bzoj-1296[SCOI2009]粉刷匠(dp)

题目链接：

[SCOI2009]粉刷匠

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1613 Solved: 922

Description

windy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数，N M T。接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

Sample Input

3 6 3
111111
000000
001100

Sample Output

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

题意：

思路：

dp[i][j][k]表示前j行一共刷i次,第j行刷k次的最多格子数;

num[i][j][s][e]表示第i行[s,e]刷j次的最多格子数,

che[i][s][e]表示第i行[s,e]刷一次的最多格子数,==num[i][j][s][e];

num的转移方程为num[i][j][s][e]=max(num[i][j-1][s][mid]+che[i][mid+1][e])

dp的转移方程是dp[i][j][k]=max(dp[i-k][j-1][x]+num[i][k][1][m]);

AC代码：

#include <bits/stdc++.h>
/*
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define For(i,j,n) for(int i=j;i<=n;i++)
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef  long long LL;
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}

const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=2e5+10;
const int maxn=1005;
const double eps=1e-10;

int n,m,t;
char mp[51][51];
LL dp[2502][51][51],che[51][51][51],num[51][51][51][51];

void Init()
{
    For(i,1,n)
    {
        For(j,1,m)
        {
            int a=0,b=0;
            For(k,j,m)
            {
                if(mp[i][k]=='1')a++;
                else b++;
                che[i][j][k]=max(a,b);
                //cout<<che[i][j][k]<<"$$$"<<endl;
            }
        }
    }
    For(i,1,n)
    {
        /*
        for(int s=1;s<=m;s++)
        {
            for(int e=s;e<=m;e++)
            {
                num[i][1][]
            }

        }*/
        For(j,1,m)
        {

            for(int s=1;s<=m;s++)
            {
                for(int e=s;e<=m;e++)
                {
                    for(int mid=s-1;mid<=e;mid++)
                    {
                        num[i][j][s][e]=max(num[i][j-1][s][mid]+che[i][mid+1][e],num[i][j][s][e]);
                    }
                }
            }
        }
    }
}




int main()
{
        read(n);read(m);read(t);
        For(i,1,n)scanf("%s",mp[i]+1);
        Init();
        mst(dp,0);
        //dp[i][a][b];前a行一共刷i次,第a行刷b次;


        For(i,1,t)
        {
            For(j,1,n)
            {

                For(k,1,m)
                {
                    For(x,0,m)
                    {
                        //cout<<dp[i][j][k]<<" "<<i<<" "<<j<<" "<<k<<endl;
                        if(i>=k)dp[i][j][k]=max(dp[i-k][j-1][x]+num[j][k][1][m],dp[i][j][k]);
                    }
                }
            }
        }
        LL ans=0;
        for(int i=1;i<=m;i++)
        {
            //cout<<dp[t][n][i]<<endl;
            ans=max(ans,dp[t][n][i]);
        }
        cout<<ans<<"
";


        return 0;
}