[DP][子序列][有限状态机][正则表达式] codeforces 1096D Easy Problem

题目链接

题意：

给一个长为1e5的串，问至少去掉多少个字符后该串中不包含hard这个子序列。

题解：

连续两场有类似的这样的题目搞砸了，心情复杂。

这个是比较简单的版本，当时真的怎么就没想到用有限状态机来表示呢。。。还是naive，太菜了。。。

用 dp[i][j] 表示到第 i 个位置为止，使得前缀为j长度的hard的子串不出现至少需要删除多少个字符。状态转移很简单，当为char==h&&j==0的时候dp[i][j]=dp[i-1][j]+1;
其他的就是枚举最后一步决策，按照删当前的还是不删当前的来分就行了。

这题搞砸真的非常难过，非常难过

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=998244353;
 
int n;
char str[maxn];
ll dp[maxn][6],w[maxn];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>(str+1);
    for(int i=1;i<=n;++i){
        cin>>w[i];
    }
    cout<<str<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=4;++j){
            if(str[i]=='h'&&j==1){
                //dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1);
                dp[i][j]=dp[i-1][j]+w[i];
            }else if(str[i]=='a'&&j==2){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+w[i]);
            }else if(str[i]=='r'&&j==3){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+w[i]);
            }else if(str[i]=='d'&&j==4){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+w[i]);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
            //dp[i][j]=(dp[i][j])%mod;
        }
    }
    cout<<dp[n][4];
    return 0;
}