显然是DP

但是交换会改变后面的状态，好像很麻烦

我们设 f [ i ] [ j ] [ k ] 表示到了第 i 个字符，j 交换了 j 次，k 交换了 k 次后最多的匹配数

我们每次只考虑当前要改变的字符，而不考虑具体跟谁交换

那么在一个状态中，如果j > k 说明还有 j-k 个 'j' 目前找不到交换目标，但是经过后面的转移或许可以找到匹配

k > j 的情况也差不多意思

有点像是先欠着到时候再还

转移也不难 ,代码里有说明

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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;}