cf Educational Codeforces Round 57 D. Easy Problem

원제: D. Easy Problem
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output
Vasya is preparing a contest, and now he has written a statement for an easy problem. The statement is a string of length n consisting of lowercase Latin latters. Vasya thinks that the statement can be considered hard if it contains a subsequence hard; otherwise the statement is easy. For example, hard, hzazrzd, haaaaard can be considered hard statements, while har, hart and drah are easy statements.
Vasya doesn’t want the statement to be hard. He may remove some characters from the statement in order to make it easy. But, of course, some parts of the statement can be crucial to understanding. Initially the ambiguity of the statement is 0, and removing i-th character increases the ambiguity by ai (the index of each character is considered as it was in the original statement, so, for example, if you delete character r from hard, and then character d, the index of d is still 4 even though you delete it from the string had).
Vasya wants to calculate the minimum ambiguity of the statement, if he removes some characters (possibly zero) so that the statement is easy. Help him to do it!
Recall that subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Input The first line contains one integer n (1≤n≤105) — the length of the statement.
The second line contains one string s of length n, consisting of lowercase Latin letters — the statement written by Vasya.
The third line contains n integers a1,a2,…,an (1≤ai≤998244353).
Output Print minimum possible ambiguity of the statement after Vasya deletes some (possibly zero) characters so the resulting statement is easy.
Examples input 6 hhardh 3 2 9 11 7 1 output 5 inputCopy 8 hhzarwde 3 2 6 9 4 8 7 1 output 4 input 6 hhaarr 1 2 3 4 5 6 output 0 Note
In the first example, first two characters are removed so the result is ardh.
In the second example, 5-th character is removed so the result is hhzawde.
In the third example there’s no need to remove anything.
중국어:
길이가 n이고 문자마다 권한이 있는 문자열을 드리겠습니다. 이 문자열의 일부 문자를 제거하여 이 문자열에 하드라는 문자열의 하위 문자열이 존재하지 않도록 합니다. 하드 하위 문자열이 존재하는 조건을 판단하자면 하드 문자열 사이에 0에서 여러 문자가 존재하고, 일부 문자를 제거한 후 하드라는 문자열의 하위 문자열이 존재하지 않는 상황에서 삭제된 문자열의 권한과 최소를 충족시킵니다.
코드:

#include 

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+5;
const ll inf = 1e18;
ll gcd(ll a,ll b)
{
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
ll dp[maxn][5],a[maxn];
int n;
string s;
string hard="hard";

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        cin>>s;
        for(int i=1;i<=n;i++)
            cin>>a[i];

        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<5;j++)
                dp[i][j]=inf;
        }
        ll ans=inf;
        for(int i=1;i<=4;i++)
            dp[0][i]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<5;j++)
            {
                if(s[i-1]!=hard[j-1])
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i]);

                if(i==n)
                {
                    ans=min(ans,dp[i][j]);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

아이디어:
이 문제는 우선 최적화할 수 있다. 모든 비hard 자모는 모두 제거할 수 있고 첫 번째 자모 h 이전에 나타난 자모도 모두 제거할 수 있다. 첫 번째 h와 첫 번째 a 사이에 나타난 비h 자모도 모두 제거할 수 있다. 같은 이치로 다른 자모도 제거할 수 있고 마지막에 남은 자모는 동적 기획으로 연산할 수 있다.
이 문제의 관건은 함께 지내는 상태가 무엇을 보존하는가에 있다
dp[i][j]dp[i][j]dp[i][j]를 설정하면 앞의 i 자모에 Hard라는 문자열 앞의 j 문자열 접두사의 최소 값을 포함합니다
그러면 i번째 문자를 고려하면 i번째 문자가 ha r d [j] hard[j] hard[j]와 다르면 dp [i] [j] = dp [i-3] [j] dp[i] [j] = dp[i-1] [j] dp[j] dp[i] [j] = dp[i] = dp[i-3 1] [j]는 i번째 문자를 건너뛰는 것을 표시하고 그렇지 않으면 i번째 문자열이 보류될지 제거될지 선택권이 작은 상태를 고려한다.
만약 i번째 문자를 보존한다면 dp [i] [j] = dp [i-3-1] [j-3] dp[i] [j]=dp[i-1] [j-1] dp[i] [j]=dp[i-3] [j-1]
만약 i번째 문자를 없애면 dp[i][j] = dp[i-3-1][j] + a[i] dp[i] [j] = dp[i-1] [j] + a[i] dp[i] [j] = dp[i-1] [j] + a[i], 그 중에서 a[i] a[i] a[i] a[i]는 i번째 문자의 권한값이다.
마지막으로 h,ha,har 및 hard 이 네 개의 자열을 포함하는 최소값을 계산하면 됩니다. 왜냐하면 이 네 개의 자열 중 하나를 빼면'hard'를 파괴할 수 있기 때문입니다.