CF1096D.Easy Problem（DP） 1800

题意

题目链接：Problem - D - Codeforces
给你一个字符串$s$，每个位置都有一个权值$a_i(1\leq n\leq 10^5)$，这个权值是删除代价，请问删除若干个字符最后没有"hard"字符的子序列的最小代价是多少？

思路

看到子序列就要往DP方面想

这是一道DP题，首先定义一个二维数组dp[i][j]。表示是到第i个字符j状态的最小值。
- dp[i][1]：不能有h
- dp[i][2]：不能有ha,可以有h
- dp[i][3]：不能有har,可以有ha
- dp[i][4]：不能有hard,可以有har
如果s[i]是"hard"的第j个字符，那么有
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]+a[i]
dp[i-1][j-1]代表不含有j状态的上一个，可以包含当前字母，dp[i-1][j]代表含有j状态上一个，但是不包含当前字母，需要加上a[i]

然后可以优化成一维的，每次只需要上一次的。
那么不在"hard"中怎么办，直接continue即可。

代码

int dp[5],pre[5];
map<char,int> mp;
inline void Case_Test()
{
    cin>>n>>s;
    for (int i=0;i<n;i++) cin>>a[i];
    mp['h']=1;mp['a']=2;mp['r']=3;mp['d']=4;
    for (int i=0;i<n;i++)
    {
        if (mp.find(s[i])==mp.end()) continue;
        int j = mp[s[i]];
        if (j==1) dp[j]+=a[i];
        else dp[j] = Min(dp[j-1],dp[j]+a[i]);
    }
    cout<<dp[4];
}