自动搬运

查看原文

来自洛谷，原作者为

	hzoi_liuchang AFO

搬运于2025-08-24 21:21:22，当前版本为作者最后更新于2020-07-15 19:15:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

我们设$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;
}