P1136 迎接仪式

#include<bits/stdc++.h>

using namespace std;

int n,m;
char a[555];
int ans=-1111;
int dp[555][111][111][3];
char flag[555];
//@xjz 

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    cin>>a+1;
    
    memset(dp,-10101,sizeof(dp));
    //赋初值 
//    mcopy();
    dp[0][0][0][1]=0;
    //开头的还没有改变 
    //i位改变j个j和k个z，当前为z（1）j（0）.... 
    for(int i=1;i<=n;i++)
    {//一共n个 
        for(int j=0;j<=m;j++)
        {//最多m次 
            for(int k=0;k<=m;k++)
            {
                //我们考虑当前字串，然后考虑它的状态 
                dp[i][j][k][a[i]==‘z‘]=max(dp[i-1][j][k][0]+(a[i]==‘z‘),dp[i-1][j][k][1]);
                //他是上个的j状态， 
                if(a[i]==‘z‘)//这一位是‘z‘  
                {
                if(k)//如果改变过‘z‘ ,尝试和之前状态更新 
                dp[i][j][k][0]=max(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]);
                }
                
                else if(j)//如果改变过‘j‘ ,尝试和之前状态更新
                dp[i][j][k][1]=max(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
                //            
            }
            
        }
        
    }
    for(int i=0;i<=m;i++)
    ans=max(ans,max(dp[n][i][i][0],dp[n][i][i][1]));
    //我们最后要看改变了m个以内中的最大值 
    
    
    cout<<ans;
    
    return 0;
}