P1136 迎接仪式
$O(n^{2}k)$：$f[i][k]$表示到第$i$个字符为止，交换$k$次，得到的最多子串数
那么枚举位置$j$，状态可以从$f[j][k-1]+1$转移过来
$O(nk^{2})$：$f[i][j][k]$表示到第$i$个字符为止，$j$个$“j”$字符转换成$“z”$，$k$个$“z”$字符转换成$“j”$的价值。
枚举4种状态：$“zj”,"zz","jj","jz"$，分别转移即可。
#include<iostream> #include<cstdio> #include<cstring> #define re register using namespace std; int max(int &a,int &b){return a>b?a:b;} int n,k,ans,f[505][105][105]; char a[505]; int main(){ scanf("%d%d",&n,&k); scanf("%s",a+1); memset(f,128,sizeof(f));//初始化极小值 f[1][0][0]=f[0][0][0]=f[1][a[1]=='j'][a[1]=='z']=0; for(re int i=2;i<=n;++i) for(re int j=0;j<=k;++j) for(re int u=0;u<=k;++u){ f[i][j][u]=f[i-1][j][u]; if(a[i-1]=='j'&&a[i]=='z') f[i][j][u]=max(f[i][j][u],f[i-2][j][u]+1); if(j&&a[i-1]=='j'&&a[i]=='j') f[i][j][u]=max(f[i][j][u],f[i-2][j-1][u]+1); if(u&&a[i-1]=='z'&&a[i]=='z') f[i][j][u]=max(f[i][j][u],f[i-2][j][u-1]+1); if(j&&u&&a[i-1]=='z'&&a[i]=='j') f[i][j][u]=max(f[i][j][u],f[i-2][j-1][u-1]+1); } for(re int i=1;i<=k;++i) ans=max(ans,f[n][i][i]);//交换就是'j','z'修改的个数相同 printf("%d",ans); return 0; }