本文共 2630 字，大约阅读时间需要 8 分钟。
Vasya is preparing a contest, and now he has written a statement for an easy problem. The statement is a string of length $ n n 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 0 0$, and removing $ i i i$-th character increases the ambiguity by $ a i a_i 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 4 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 n n$ ($ 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105$) — the length of the statement.The second line contains one string $ s s s$ of length $ n n n$, consisting of lowercase Latin letters — the statement written by Vasya.
The third line contains $ n n n$ integers $ a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an$ ($ 1 ≤ a i ≤ 998244353 1 \le a_i \le 998244353 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 Input 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 5 5$-th character is removed so the result is hhzawde.
In the third example there’s no need to remove anything.
题意很简单，就是删除字符，使之没有hard子序列。问最小的花费是多少。 这种题目就是看删除前面字符对于后面的影响。dp[0~3]分别代表着删除h到d的最小花费。举个例子，就像hhard这种的，遇见a的时候，我们会想是单纯的删除a价值小，还是删除两个h价值小。这样就有了递推公式：dp[i]=min(dp[i-1],dp[i]+a[i])。 代码如下：#include#define ll long long#define inf 0x7f7f7f7fusing namespace std;const int maxx=1e6+100;ll dp[10];ll a[maxx];string s;int n;int main(){ while(~scanf("%d",&n)) { cin>>s; for(int i=0;i
dp一定多想想，有时候没有看起来那么难！
努力加油a啊，(o)/~转载地址：http://dytvi.baihongyu.com/