[CF1096D] hard

今天你$hard$hard吗？

• 哎，还是状态的定义啊……菜鸡又要看博客了。
• 设$f[i][j]$f[i][j]表示到了第$i$i个点，不能到达$j$j状态的最小代价。
• 如果此时$j与i$j与i匹配上了，$f[i][j]=min(f[i-1][j-1],f[i-1][j]+a[i])$f[i][j]=min(f[i−1][j−1],f[i−1][j]+a[i])；
• 否则，$f[i][j]=f[i-1][j]$f[i][j]=f[i−1][j]。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int n,m,a[N];ll f[N][5];
int main(){
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<5;++i) f[0][i]=0;
	t[1]='h',t[2]='a',t[3]='r',t[4]='d';
	for(int i=1;i<=n;++i){
		for(int j=1;j<=4;++j){
			if(s[i]==t[j]){
				f[i][j]=min(f[i-1][j-1],f[i-1][j]+a[i]);
			}else
				f[i][j]=min(f[i][j],f[i-1][j]);
		}
	}
	cout<<min(min(f[n][4],f[n][3]),min(f[n][1],f[n][2]))<<endl;
	return 0;
}