【BZOJ 1296】 [SCOI2009]粉刷匠

在这里输入题意

【题解】

f[i][j][k]表示第i行前j列刷了k次，最大满意度
f[][j][k]=max{f[i][l][k],f[i][l][k-1]+max{zero(l+1,j),one(l+1,j)} }

g[i][j]表示前i行刷了j次的最大满意度。

g[i][j]=max{g[i-1][j-k] + f[i][m][k]}

取max{g[n][0..t]}就好

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int N = 50;

int f[N+10][N+10][N+10],a[N+10][N+10],n,m,t,b[N+10][N+10][2],g[N+10][N*N+10];

char s[N+10][N+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m >> t;

    rep1(i,1,n)

        cin >> (s[i]+1);

    rep1(i,1,n)

        rep1(j,1,m){

            a[i][j] = s[i][j]-'0';

            for (int k = 0;k <= 1;k++) b[i][j][k] = b[i][j-1][k];

            b[i][j][a[i][j]]++;

        }

    rep1(i,1,n)

        rep1(j,1,m)

            rep1(k,0,j){

                rep1(l,0,j-1){

                    f[i][j][k] = max(f[i][j][k],f[i][l][k]);

                    if (k>0) f[i][j][k] = max(f[i][j][k],f[i][l][k-1]+ max(b[i][j][0]-b[i][l][0],b[i][j][1]-b[i][l][1]));

                }

            }

    rep1(i,1,n)

        rep1(j,0,N*N)

            rep1(k,0,N)

                if (j-k>=0)

                    g[i][j] = max(g[i][j],g[i-1][j-k]+f[i][m][k]);

                    else break;

    int ans = 0;

    rep1(i,0,t) ans = max(ans,g[n][i]);

    cout<<ans<<endl;

	return 0;

}

巴特西

【BZOJ 1296】 [SCOI2009]粉刷匠

最新文章

热门文章