by luogu
范围
一个dp题
#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; }