题解 P1136 【迎接仪式】

· · 题解

分析

我们设f[i][j][k][0]为遍历了字符串的前i位，改变了j个j和k个z，并且当前的这一位为j所能达到的最大价值

设f[i][j][k][1]为遍历了字符串的前i位，改变了j个j和k个z，并且当前的这一位为z所能达到的最大价值

我们先来考虑f[i][j][k][0]

如果该字符串的第i位本来是z，那么我们把它改为j后，必定不会与前面的字符组成jz，而且必定会花费一次修改操作

因此当前的最大值应该在前面的字符变为j或变为z中取

f[i][j][k][0]=max(f[i-1][j][k-1][0],f[i-1][j][k-1][1]);

如果该字符串的第i位本来是j，那么我们就不需要进行修改操作

但是，当前的字符仍然不会与前面的字符组成jz

所以当前的最大值还应该在前面的字符变为j或变为z中取

f[i][j][k][0]=max(f[i-1][j][k][0],f[i-1][j][k][1]);

接下来我们再考虑f[i][j][k][1]

如果该字符串的第i位本来是z,那么如果上一位的字符为j，那么又可以组成一个jz,如果上一位为j，则不能组成

f[i][j][k][1]=max(f[i-1][j][k][0]+1,f[i-1][j][k][1]);

如果该字符串的第i位本来是j，那么我们就需要进行一次修改操作

f[i][j][k][1]=max(f[i-1][j-1][k][0]+1,f[i-1][j-1][k][1]);

最后我们再在j和k相等的方案中取一个最大值即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=505,maxk=105;
int n,m,f[maxn][maxk][maxk][3];
char s[maxn];
int main(){
    scanf("%d%d%s",&n,&m,s+1);
    memset(f,128,sizeof(f));
    f[0][0][0][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=m;k++){
                if(s[i]=='z'){
                    f[i][j][k][1]=max(f[i-1][j][k][0]+1,f[i-1][j][k][1]);
                    if(k) f[i][j][k][0]=max(f[i-1][j][k-1][0],f[i-1][j][k-1][1]);
                } else {
                    f[i][j][k][0]=max(f[i-1][j][k][0],f[i-1][j][k][1]);
                    if(j) f[i][j][k][1]=max(f[i-1][j-1][k][0]+1,f[i-1][j-1][k][1]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,max(f[n][i][i][1],f[n][i][i][0]));
    }
    printf("%d\n",ans);
    return 0;
}