题目描述

题解

我们可以设$f[i][1/2/3/4]$f[i][1/2/3/4]表示前i位，每一个数字分别到$h,a,r,d$h,a,r,d不满足的方案数。即，$f[1]$f[1]表示不存在子序列h，$f[2]$f[2]表示不存在子序列$ha$ha，$f[3]$f[3]表示不存在子序列$har$har，$f[4]$f[4]表示不存在子序列$hard$hard。

对于求解$f[i][j]$f[i][j],可以分成四种情况：

• 当$a[i]=h$a[i]=h时，$f[i][j]=f[i-1][1]+val[i].$f[i][j]=f[i−1][1]+val[i].
• 当$a[i]=h$a[i]=h时，$f[i][j]=min(f[i-1][1],f[i-1][2]+val[i]).$f[i][j]=min(f[i−1][1],f[i−1][2]+val[i]).要么就不要让$h$h存在，$a$a可以单独存在；要么就让$h$h存在，这个消掉。
• 当$a[i]=r$a[i]=r时，$f[i][j]=min(f[i-1][2],f[i-1][3]+val[i])$f[i][j]=min(f[i−1][2],f[i−1][3]+val[i]).
• 当$a[i]=d$a[i]=d时，$f[i][j]=min(f[i-1][3],f[i-1][4]+val[i]).$f[i][j]=min(f[i−1][3],f[i−1][4]+val[i]).
• 否则$f[i][0/2/3/4]=f[i-1][1/2/3/4]$f[i][0/2/3/4]=f[i−1][1/2/3/4]

然而滚动数组很好写啊。

#include <bits/stdc++.h>

#define int long long 

using namespace std;

int n;
int v[1000000];
int f[1000000];
char a[1000000];

signed main(void)
{
	cin>>n>>a+1;
	for (int i=1;i<=n;++i) scanf("%lld", v+i);
	for (int i=1;i<=n;++i)
	{
		if (a[i] == 'h') f[1] += v[i];
		if (a[i] == 'a') f[2] = min(f[1],f[2]+v[i]);
		if (a[i] == 'r') f[3] = min(f[2],f[3]+v[i]);
		if (a[i] == 'd') f[4] = min(f[3],f[4]+v[i]);
	}	
	cout<<f[4]<<endl;
	return 0;
}