题解 P4158 【[SCOI2009]粉刷匠】

· · 题解

解题思路

一开始读错了题，没看到只能刷一遍，白费了半个小时。 然后突然发现原来每个格子只能刷一遍啊，那就直接开状态DP了。

设dp[i][j][k][0/1]表示刷到第i行第j列再刷第k次将当前格刷成红/蓝的最优值。 转移显然，注意换行时特判。

if(j==1){
    if(ch[i][j]=='0')
        dp[i][j][q][0]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1])+1,
        dp[i][j][q][1]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1]);
    if(ch[i][j]=='1')
        dp[i][j][q][1]=max(dp[i-1][m][q-1][1],dp[i-1][m][q-1][0])+1,
        dp[i][j][q][0]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1]);
    continue;
}
if(ch[i][j]=='0')
    dp[i][j][q][0]=max(dp[i][j-1][q-1][1],dp[i][j-1][q][0])+1,
    dp[i][j][q][1]=max(dp[i][j-1][q-1][0],dp[i][j-1][q][1]);
if(ch[i][j]=='1')
    dp[i][j][q][1]=max(dp[i][j-1][q-1][0],dp[i][j-1][q][1])+1,
    dp[i][j][q][0]=max(dp[i][j-1][q-1][1],dp[i][j-1][q][0]);

WA了一次是因为第三重循环没从1开始，本来是想优化下时间，不料却弄巧成拙，果然提前的优化都是负优化。

AC代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,dp[60][60][3000][2],ans(0);
char ch[60][60];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
        cin>>ch[i]+1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int q=max(1,i-1);q<=min(k,(i-1)*m+j);++q){
                if(j==1){
                    if(ch[i][j]=='0')
                        dp[i][j][q][0]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1])+1,
                        dp[i][j][q][1]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1]);
                    if(ch[i][j]=='1')
                        dp[i][j][q][1]=max(dp[i-1][m][q-1][1],dp[i-1][m][q-1][0])+1,
                        dp[i][j][q][0]=max(dp[i-1][m][q-1][0],dp[i-1][m][q-1][1]);
                    continue;
                }
                if(ch[i][j]=='0')
                    dp[i][j][q][0]=max(dp[i][j-1][q-1][1],dp[i][j-1][q][0])+1,
                    dp[i][j][q][1]=max(dp[i][j-1][q-1][0],dp[i][j-1][q][1]);
                if(ch[i][j]=='1')
                    dp[i][j][q][1]=max(dp[i][j-1][q-1][0],dp[i][j-1][q][1])+1,
                    dp[i][j][q][0]=max(dp[i][j-1][q-1][1],dp[i][j-1][q][0]);
            }
    for(int i=1;i<=k;++i)
        ans=max(dp[n][m][i][0],max(ans,dp[n][m][i][1]));
    cout<<ans;
    return 0;
}