题意
给出一个串 给出删除每一个字符的代价问使得串里面没有 hard 的子序列需要付出的最小代价 (子序列不连续也行)
思路
要满足 hard 先要满足 har 要满足 har 先要满足 ha 一次类推
这类问题的一个共同点是要每个地方都要满足一系列前置条件才能成立也就是说有衔接关系
所以如果是构造问题 那么 dp 数组加一维已经满足了几个, 如果是删除问题 dp 数组加一维 切断了哪一个即可
所以我们可以设置 dp 数学 dp[i][1,2,3,4] 表示在 i 位置时 字符是 h,a,r,d 对应于 1,2,3,4 使得以 h,a,r,d 为前缀不存在的所需要消耗的最小代价是多少
这样 \(dp[i][1]=dp[i-1][1]+a[i]\) 表示要使得 h 不存在 有 h 就要删掉 h
\(dp[i][2]=max(dp[i-1][1],dp[i-1][2]+a[i])\) 要使得 ha 不存在 要么没有 h 要么没有 a
\(dp[i][3]=max(dp[i-1][2],dp[i-1][3]+a[i])\) 要使得 har 成立 要么没有要么 a 要么没有 r
\(dp[i][4]=max(dp[[i-1][3],dp[i-1][4]+a[i])\) 同上
注意 这里 i 可以用滚动数组滚掉节省空间 不然开不下 记得开 long long
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 3e5+5;
- #define int long long
- #define F first
- #define S second
- #define pb push_back
- #define pii pair<int ,int>
- #define mkp make_pair
- const int inf=0x3f3f3f3f;
- char s[maxn];
- int a[maxn];
- int dp[10];
- int32_t main(){
- int n;
- scanf("%lld",&n);
- scanf("%s",s+1);
- for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
- for(int i=1;i<=n;i++){
- if(s[i]=='h')dp[1]=dp[1]+a[i];
- if(s[i]=='a')dp[2]=min(dp[1],dp[2]+a[i]);
- if(s[i]=='r')dp[3]=min(dp[2],dp[3]+a[i]);
- if(s[i]=='d')dp[4]=min(dp[3],dp[4]+a[i]);
- }
- cout<<dp[4]<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3043010.html