P4158 [SCOI2009]粉刷匠

· · 题解 

dp题啊，俗话说dp有两难，一者为找状态，另一者为状态转移，但是 

 前者找不到，显然后者更不会啊！不过好在这是道线性dp的题，线性dp
 主要看你最后想要的状态，实际上可以根据你想要的状态倒推你需
 要什么状态，不如让我们切入正题。这道题你想知道全部的木块最
 多有多少是正确染色的，因此你需要找切入点了，我需要判断前面
 一些的状态。这时候你发现每一行都是独立的所以每一行都应该作
 为状态。还需要考虑每次染色的独立性。因此我们用f[i][j]表示
 前行共染了j次的最大正确数。

然后我陷入了深思（然后呢）好吧人类智慧来了

既然我已经确定了前i行的状态，我怎么转移呢，转念一想似乎需要
确定每一行的转移。因此诞生了g数组。我用g[i][j][k]表示前i行
用了j次粉刷机会，涂了k个颜色块。所以呢？如何状态转移呢？
    for(int i=1;i<=n;i++)
    for(int j=1;j<=t;j++)
    for(int k=1;k<=min(j,m);k++)
    f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);

对，我们处理了f数组，g数组也需要处理啊！

人类智慧又来了

g数组的处理又将何去何从。其实可以这样

 for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=1;k<=m;k++)
    for(int q=j-1;q<k;q++)
    g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-sum[i][k]+sum[i][q]));

而sum数组就是染成蓝色的数量。这道题就可以结束了。dp题的套路也就结束了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int t,n,m;
char s[60];
int sum[60][60],g[60][60][60],f[60][3000],ans;

int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
    sum[i][0]=0;
    scanf("%s",s+1);
    for(int j=1;j<=m;j++){
    if(s[j]-'0'==1) sum[i][j]=sum[i][j-1]+1;
    else sum[i][j]=sum[i][j-1];
    }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=1;k<=m;k++)
    for(int q=j-1;q<k;q++)
    g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-sum[i][k]+sum[i][q]));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=t;j++)
    for(int k=1;k<=min(j,m);k++)
    f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);
    ans=0;
    for(int i=1;i<=t;i++) ans=max(ans,f[n][i]);
    cout<<ans<<endl;
    return 0;
}