显然是DP
但是交换会改变后面的状态，好像很麻烦
我们设 f [ i ] [ j ] [ k ] 表示到了第 i 个字符，j 交换了 j 次，k 交换了 k 次后最多的匹配数
我们每次只考虑当前要改变的字符，而不考虑具体跟谁交换
那么在一个状态中，如果j > k 说明还有 j-k 个 'j' 目前找不到交换目标，但是经过后面的转移或许可以找到匹配
k > j 的情况也差不多意思
有点像是先欠着到时候再还
转移也不难 ,代码里有说明
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=507,INF=1e9+7; int n,m,ans; int f[N][107][107]; char a[N]; int main() { n=read(); m=read(); scanf("%s",a+1); for(int i=0;i<=m;i++) for(int j=0;j<=m;j++) f[0][i][j]=f[1][i][j]=-INF;//初始化 f[0][0][0]=f[1][0][0]=f[1][a[1]=='j'][a[1]=='z']=0;//特殊考虑i=1的情况 for(int i=2;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=m;k++) { f[i][j][k]=f[i-1][j][k];//不进行任何交换 if(a[i-1]=='j'&&a[i]=='z') { f[i][j][k]=max(f[i][j][k],f[i-2][j][k]+1); continue; }//不交换也有匹配 if(a[i-1]=='j'&&a[i]=='j'&&j) { f[i][j][k]=max(f[i][j][k],f[i-2][j-1][k]+1); continue; }//把后面的j换掉，增加匹配 if(a[i-1]=='z'&&a[i]=='j'&&j&&k) { f[i][j][k]=max(f[i][j][k],f[i-2][j-1][k-1]+1); continue; }//把两个字符一起换掉，增加匹配 if(a[i-1]=='z'&&a[i]=='z'&&k) f[i][j][k]=max(f[i][j][k],f[i-2][j][k-1]+1);//把前面的z换掉，增加匹配 } for(int i=0;i<=m;i++) ans=max(ans,f[n][i][i]); printf("%d",ans); return 0; }