題目大意：

現在有一個由小寫字母組成的字符串，去掉這個字符串的第i個位置的字符會有ai的代價。你的任務是去掉這個字符串中的一些字符使得該字符串中不包含子序列hard，且去掉字符的代價之和盡可能小。

輸入

第一行一個整數n表示字符串的長度(1<=n<=100000)。 第二行一個給定的字符串。 第三行n個整數a1,a2,a3,...,an(1<=ai<=998244353)。

輸出

輸出一個整數表示答案。

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,?55-th character is removed so the result is?hhzawde.

In the third example there's no need to remove anything.

解題報告：

考慮dp。首先有效字符只有hard四個字符，考慮轉移。

如果出現不合法序列，最后一個字符肯定是d，并且前面按照順序出現了har，所以可以設定dp[n][4]代表前綴不出現h，不出現ha，不出現har，不出現hard的最小代價。最后dp[n][4]就是答案。

轉移就是對于四個字符中的每一個字符，假設是d，那么更新dp[i][4]，則選擇刪除或者不刪除這個字符，如果刪除則從dp[i-1][4]+a[i]轉移過來，如果不刪除則需要保證前i-1個字符不能有har，所以dp[i-1][3]轉移過來。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; char s[MAX]; int n,a[MAX]; ll dp[MAX][5];//h a r d int main() {memset(dp,0x3f,sizeof dp);for(int j = 1; j<=4; j++) dp[0][j] = 0; cin >> n;cin >> s+1;for(int i = 1; i<=n; i++) cin >> a[i];for(int i = 1; i<=n; i++) {for(int j = 1; j<=4; j++) dp[i][j] = dp[i-1][j];if(s[i] == 'h') dp[i][1] = dp[i-1][1]+a[i];if(s[i] == 'a') dp[i][2] = min(dp[i-1][2]+a[i],dp[i-1][1]);if(s[i] == 'r') dp[i][3] = min(dp[i-1][3]+a[i],dp[i-1][2]);if(s[i] == 'd') dp[i][4] = min(dp[i-1][4]+a[i],dp[i-1][3]);}printf("%lld\n",*min_element(dp[n]+1,dp[n]+5));return 0 ; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1096D】Easy Problem（dp，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。