#include<bits/stdc++.h>
using namespace std;
char s[100007];
long long a[100007];
long long dp[100007][4];
int main(){
int n;
scanf("%d",&n);
scanf("%s",s);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
for(int i=0;i<n;i++){
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2];
dp[i][3]=dp[i-1][3];
if(s[i]==‘h‘)
dp[i][0]+=a[i],dp[i][1]=min(dp[i-1][0],dp[i-1][1]);//字符串中没有长度为1的子序列付出的代价
else if(s[i]==‘a‘)
dp[i][1]+=a[i],dp[i][2]=min(dp[i-1][1],dp[i-1][2]);//字符串中没有长度为2的子序列付出的代价
else if(s[i]==‘r‘)
dp[i][2]+=a[i],dp[i][3]=min(dp[i-1][2],dp[i-1][3]);//字符串中没有长度为3的子序列付出的代价
else if(s[i]==‘d‘)
dp[i][3]+=a[i];//字符串中没有hard付出的代价
}
long long ans=1e18;
for(int i=0;i<4;i++)
ans=min(ans,dp[n-1][i]);
printf("%lld",ans);
return 0;
}
Educational Codeforces Round 57D（DP，思维）
原文：https://www.cnblogs.com/ldudxy/p/10411852.html