- /*
- 没想到scoi也有这么水的题。。。
- 首先对于每个格子不管刷什么颜色,刷肯定比不刷更优,所以设
- dp[i][j][k][0/1]表示刷到i行j列用了k次并且这一格刷的是红/蓝的最大值。
- 然后转移即可。
- */
- #include
- #include
- #defineN 60#defineM 2510using namespace std;
- intdp[N][N][M][2],n,m,T;
- char a[N][N];
- int main(){
- scanf("%d%d%d",&n,&m,&T);
- for(inti=1;i<=n;i++) scanf("%s",a[i]+1);
- for(inti=1;i<=n;i++)
- for(intj=1;j<=m;j++)
- for(intk=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])+(a[i][j]=='0');
- dp[i][j][k][1]=max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])+(a[i][j]=='1');
- }
- else {
- dp[i][j][k][0]=max(dp[i][j-1][k][0],dp[i][j-1][k-1][1])+(a[i][j]=='0');
- dp[i][j][k][1]=max(dp[i][j-1][k][1],dp[i][j-1][k-1][0])+(a[i][j]=='1');
- }
- }
- intans=0;
- for(inti=1;i<=T;i++)
- ans=max(ans,max(dp[n][m][i][0],dp[n][m][i][1]));
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2039424.html