【DP】CF1096D Easy Problem

比眉伴天荒 2024-03-26 20:33 70阅读 0赞

题意：

现在有一个由小写字母组成的[字符串][Link 1]，去掉这个字符串的第i个位置的字符会有ai的代价。你的任务是去掉这个字符串中的一些字符使得该字符串中不包含子序列hard，且去掉字符的代价之和尽可能小。

思路：

感觉这个状态设计有点难想

对于短小的子序列，一般去考虑维护前缀s1,s1~s2,s1~s3....的数量

状态设计：

首先去考虑它影响决策的因素：序列中是否含有hard子序列

这个条件怎么去处理？**这个条件肯定是要体现在状态里的**

因此我们可以**试着**进行状态设计，**还得去考虑答案能不能这样统计**

设

dp\[i\]\[1\]表示前缀不含h的最小花费

dp\[i\]\[2\]表示前缀不含ha的最小花费

dp\[i\]\[3\]表示前缀不含har的最小花费

dp\[i\]\[4\]表示前缀不含hard的最小花费

然后去考虑转移

转移就是对于四个字符中的每一个字符，假设是d，那么更新dp\[i\]\[4\]，则选择删除或者不删除这个字符，如果删除则从dp\[i-1\]\[4\]+a\[i\]转移过来，如果不删除则需要保证前i-1个字符不能有har，所以dp\[i-1\]\[3\]转移过来。

状态设计一定要多试！！！

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    
    
    int n;
    string s;
    int a[mxn],dp[mxn][5];
    void solve(){
        cin>>n>>s;
        s=" "+s;
        for(int i=1;i<=n;i++) cin>>a[i];
        memset(dp,0x3f,sizeof(dp));
        for(int j=1;j<=4;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=4;j++) dp[i][j]=dp[i-1][j];
            if(s[i]=='h') dp[i][1]=dp[i-1][1]+a[i];
            if(s[i]=='a') dp[i][2]=min(dp[i-1][2]+a[i],dp[i-1][1]);
            if(s[i]=='r') dp[i][3]=min(dp[i-1][3]+a[i],dp[i-1][2]);
            if(s[i]=='d') dp[i][4]=min(dp[i-1][4]+a[i],dp[i-1][3]);
        }
        int ans=1e18;
        for(int j=1;j<=4;j++) ans=min(ans,dp[n][j]);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Link 1]: https://so.csdn.net/so/search?q=%E5%AD%97%E7%AC%A6%E4%B8%B2&spm=1001.2101.3001.7020