题意:略。
题记:dp[i][j][k][0/1]表示为前i条j段涂k次,最后一段涂红/蓝的最多正确格子数。
可以理解为将所有木条分成了n*m的木块。然后一块一块地填。
那么可以分成两种情况:
1、当前木块是整条木板的第一块,一定要进行一次新的涂色。(即j为1的情况)
由上一条木条的最后一块木板转移过来
当前木块涂红色:dp[i][j][k][0]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1])+(mp[i][j]==0);
当前木块涂蓝色:dp[i][j][k][1]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1])+(mp[i][j]==1);
2、当前木块不是整条木板的第一块,根据前一块木块的颜色来
判断是否需要新的涂色。(即j不为1的情况)
由同一条木条的前一块木板转移过来
当前木块涂红色:dp[i][j][k][0]=max(dp[i][j−1][k][0],dp[i][j−1][k−1][1])+(mp[i][j]==0);
当前木块涂蓝色:dp[i][j][k][1]=max(dp[i][j−1][k][1],dp[i][j−1][k−1][0])+(mp[i][j]==1);
#include<bits/stdc++.h> using namespace std; const int N=55; char mp[N][N]; int dp[N][N][2510][2];//dp[i][j][k][0/1] //前i条j段涂k次,最后一段涂红/蓝的最多正确格子数 //红(0)蓝(1) int main(){ int n,m,t; cin>>n>>m>>t; for(int i=1;i<=n;i++) cin>>mp[i]+1; for(int i=1;i<=n;i++){//枚举第i条木板 for(int j=1;j<=m;j++){//枚举第j段 for(int k=1;k<=t;k++){//枚举涂的次数 if(j==1){ dp[i][j][k][0]=max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])+(mp[i][j]=='0'); dp[i][j][k][1]=max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])+(mp[i][j]=='1'); } else{ dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k-1][1])+(mp[i][j]=='0'); dp[i][j][k][1]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0])+(mp[i][j]=='1'); } } } } cout<<max(dp[n][m][t][0],dp[n][m][t][1])<<endl; return 0; }