题意:长度为n的字符串 删除每个位置的字符有花费 求使其没有hard的子序列的最小花费
题解:比赛首先想到的是贪心,删除每一个字母前面的所有前一个字母,但是这种只能考虑删除单一的字符,无法考虑到 harard 100 1 100 100 1 100 这种删除两种字符的情况 ，比赛结束后看题解 , 对于这种让其无法构成一种字符串的dp , 状态是构成其前缀字符串，转移便是 对于无法构成前i个前缀的最小花费 首先可以考虑让他无法构成前i-1个字符的最小花费 然后便是考虑将这个位置的字符删除 用滚动数组 dp[i] 无法构成前i个字符的最小花费
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll b[100000 + 7]; ll dp[5]; int main(){ int n ; cin >> n; string a; cin >> a; for(int i =0 ; i < n ; i++){ cin >> b[i] ; } ///只有出现了这个单词且在某个后面，才会发生转移，所以保证了能够得到最优解 for(int i = 0 ; i < n ; i++){ if(a[i] == 'h') dp[1] = dp[1] + b[i]; else if(a[i] == 'a') dp[2] = min(dp[1] ,dp[2] + b[i]); else if(a[i] == 'r') dp[3] = min(dp[2],dp[3] + b[i]); else if(a[i] == 'd') dp[4] = min(dp[3],dp[4] + b[i]); } cout << dp[4] << endl; return 0; }