我们设 $f[i][j]$ 为让原字符串满足最多包含 $\texttt{hard}$ 的前 $j$ 个字符，所需要的最小修改代价

特别的， $f[i][0]$ 表示不包含 $h$ 的最小修改代价

考虑转移方程，有两种情况

当 $s[i] \ne c[j+1]$ 时（ $c$ 是预先处理好的 $\texttt{hard}$ ），加上第 $i$ 个字符后不会增加最大匹配的长度，所以 $f[i][j]=f[i-1][j]$

当 $s[i] = c[j+1]$ ，又可以选择删与不删第 $i$ 个字符

所以 $f[i][j]=\min(f[i-1][j]+a[i],f[i-1][j-1])$

在选择不删除的时候，为了不凑出 $\texttt{hard}$ 的前 $j+1$ 个字符，我们在前面最多只能凑出前 $j-1$ （使得 $c[j+1]$ 与前面的字符断开）。

我们发现在每次转移的时候，只用到了 $f[i-1]$ 和 $f[i]$ 这两层，所以我们可以把第一维用滚动数组省略掉。

#include<cstdio>
#include<iostream>
using namespace std;
const long long Maxn=100000+10,inf=(1ll<<60);
long long f[5],a[Maxn];
char c[5]={'f','h','a','r','d'};
char s[Maxn];
long long n,ans=inf;
int main()
{
//  freopen("in.txt","r",stdin);
    scanf("%lld",&n);
    scanf("%s",s+1);
    for(long long i=1;i<=n;++i)
    scanf("%lld",a+i);
    for(long long i=1;i<=n;++i)
    for(long long j=3;j>=0;--j)
    if(s[i]==c[j+1])
    {
        f[j]+=a[i];
        if(j)f[j]=min(f[j],f[j-1]);
    }
    for(long long i=0;i<4;++i)
    ans=min(ans,f[i]);
    printf("%lld\n",ans);
    return 0;
}