[SCOI2009]粉刷匠题解

这道题你猛的一看呢没什么头绪，但你仔细一看呢，就会发现还不如猛的一看，嘿嘿，蒟蒻自己的理解如下；
看题的范围我们可以想到DP，很合适，50502500，然后就是我们dp定义的状态，看了很多大佬的 四维是真的想不到，理解的很难啊，还是太菜，蒟蒻定义一个三维一个二维，二维的很容易理解就是一个分组背包，那么关键是三维，如何把三维处理出来变成分组背包是一个技术活，首先我们定义dp[i][j][k],是什么意思呢，意思是i组涂j次k个长度的木板然后正确的个数， dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][l]+max(k-l里面最多的木板)之后处理出来就是直接分组背包搞

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int maxx=1e6+7;
const int mod=1e9+7;
int dp[55][55][3000];
char ans[55];
int pre[55];
int f[maxx];
int main()
{
    int n,m,t;
    cin>>n>>m>>t;
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ans+1);
        for(int j=1; j<=m; j++)
        {
            pre[j]=pre[j-1]+(ans[j]=='1');
        }
        for(int j=1; j<=m; j++)
            for(int k=1; k<=m; k++)
                for(int l=0; l<k; l++)
                {
                    int tep=pre[k]-pre[l];
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][l]+max(tep,k-l-tep));
                }
    }
    for(int i = 1; i <= n; i++)
        for(int k = t; k > 0; k--)
            for(int j = 1; j <= min(k, m); j++)
            {
                f[k] = max(f[k], f[k - j] + dp[i][j][m]);

            }
            cout<<f[t]<<endl;
    return 0;
}