Wannafly挑战12 C删除子串 - DP

主题链接：点击打开链接

解题思路:dp[i][0][j]从n到i的位置变为j结尾是a的最长长度，dp[i][1][j]结尾是b的最长长度。

应注意的是，转移方程不能从0长度转移。

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mx = 1e5 + 10;int n,m,a[5] = {1,2,3,5};char str[mx];int dp[mx][2][12];int main(){scanf("%d%d",&n,&m);scanf("%s",str+1);for(int j=0;j<=m;j++){for(int i=n;i>=1;i--){if(!j) dp[i][str[i]-'a'][j] = dp[i+1][str[i]-'a'][j] + 1,dp[i][(str[i]-'a')^1][j] = dp[i+1][(str[i]-'a')^1][j];else if(str[i]=='a'){if(dp[i+1][0][j]) dp[i][0][j] = max(dp[i][0][j],dp[i+1][0][j]+1);if(dp[i+1][1][j-1])dp[i][0][j] = max(dp[i][0][j],dp[i+1][1][j-1]+1); dp[i][1][j] = dp[i+1][1][j];}else{if(dp[i+1][1][j])  dp[i][1][j] = max(dp[i][1][j],dp[i+1][1][j]+1);if(dp[i+1][0][j-1]) dp[i][1][j] = max(dp[i][1][j],dp[i+1][0][j-1]+1);dp[i][0][j] = dp[i+1][0][j];}}}int ans = 0;for(int i=0;i<=m;i++) ans = max(ans,dp[1][0][i]);printf("%d\n",ans);     return 0;}