题目传送门：CF1096D
洛谷入口
题目大意：
(给出一个长度为n的字符串，如果这个字符串中含有子序列“hard”，那么这个字符串就很hard)
(你不希望这个字符串很hard，所以想要从中删掉几个字符使他不hard)
((例： hard, hzazrzd, haaaaard 都很hard，而har, hart，drah不hard))
(删掉在原字符串中的第i个字符需要花费a_i的代价，求最小代价)
数据范围
(circ) (1le nle10^5)
(circ) (1le a_ile998244353)
题解
这题我竟无言以对……
这题在洛谷竟还是蓝题！（划掉）
好了步入正题！
首先这很明显，不能贪心，无后效性，果然是—————
设立状态f[i][j]指此刻（这i的时刻）删到j位（h-1,a-2,r-3,d-4）时的花费最小值
然后开始考虑ztzyfc（状态）（转移）（方程）
f[i][j]来说，可以删j，也可以不删j，于是从两个里取个最小值
即f[i][j]=min(f[i][j-1],f[i][j]+a[i]);（就这个道理）
而对于f[i][1]，当然要直接硬让他删，于是直接加
然后，还有什么吗？
哦对就是最后答案取顺下来的f[n][4]啦！
好了准备好了吗？看代码！↓↓↓
AC代码
（本人不担心会T，于是通用流输入输出（不会说是懒））
首先，是一种最复杂的版本，也是看起来最笨的写法：
#include<bits/stdc++.h>//没的说
#define ll long long
using namespace std;
ll n,a[100010],ans,f[100010][5];
char s[100010];
int main(){
cin>>n;
scanf("%s",&s);
for(ll i=1;i<=n;i++){
cin>>a[i];
if(s[i-1]=='h')f[i][1]=f[i-1][1]+a[i],f[i][2]=f[i-1][2],f[i][3]=f[i-1][3],f[i][4]=f[i-1][4];
else if(s[i-1]=='a')f[i][2]=min(f[i-1][1],f[i-1][2]+a[i]),f[i][1]=f[i-1][1],f[i][3]=f[i-1][3],f[i][4]=f[i-1][4];
else if(s[i-1]=='r')f[i][3]=min(f[i-1][2],f[i-1][3]+a[i]),f[i][1]=f[i-1][1],f[i][2]=f[i-1][2],f[i][4]=f[i-1][4];
else if(s[i-1]=='d')f[i][4]=min(f[i-1][3],f[i-1][4]+a[i]),f[i][1]=f[i-1][1],f[i][2]=f[i-1][2],f[i][3]=f[i-1][3];
else for(int j=1;j<=4;j++)f[i][j]=f[i-1][j];
}
cout<<f[n][4];
}
然后就是稍微结合规律放在了一起，还有map：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[100010],ans,f[100010][5];
char s[100010];
map<char,int>mp;
int main(){
mp['h']=1,mp['a']=2,mp['r']=3,mp['d']=4;
cin>>n;scanf("%s",&s);
for(ll i=1;i<=n;i++){
cin>>a[i];
for(int j=1;j<=4;j++){
if(mp[s[i-1]]==j){
if(j!=1)f[i][j]=min(f[i-1][j-1],f[i-1][j]+a[i]);
else f[i][j]=f[i-1][j]+a[i];
}
else f[i][j]=f[i-1][j];
}
}
cout<<f[n][4];
}
最后还有一种近似玄学的写法
简直了，看代码，不要告诉我这是蓝题，不然题就要被降级了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans,f[5];
char s[100010];
map<char,int>mp;
int main(){
mp['h']=1,mp['a']=2,mp['r']=3,mp['d']=4;
cin>>n;scanf("%s",&s);
for(ll i=1;i<=n;i++){
ll x;cin>>x;
if(s[i-1]=='h')f[1]+=x;
if(s[i-1]=='a')f[2]=min(f[1],f[2]+x);
if(s[i-1]=='r')f[3]=min(f[2],f[3]+x);
if(s[i-1]=='d')f[4]=min(f[3],f[4]+x);
}
cout<<f[4];
}