先dp处理出每行刷\(i\)次能够正确粉刷多少个格子
然后背包
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// <1296.cpp> - 08/30/16 19:43:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } bool gc(){ char ch=getchar(); while(ch!='1'&&ch!='0')ch=getchar(); return ch=='1'; } const int MAXN=100001; const int INF=1e9; int a[60],dp[60][2600],pp[60][2600]; int main(){ int n=gi(),m=gi(),T=gi(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[j]=a[j-1]+gc(); for(int k=1;k<=T;k++){ dp[j][k]=dp[j-1][k]; for(int l=0;l<j;l++)dp[j][k]=max(dp[j][k],dp[l][k-1]+max(a[j]-a[l],j-l-a[j]+a[l])); } } for(int k=1;k<=T;k++)pp[i][k]=pp[i-1][k]; for(int k=1;k<=T;k++) for(int j=k;j<=T;j++)pp[i][j]=max(pp[i][j],pp[i-1][j-k]+dp[m][k]); } printf("%d",pp[n][T]); return 0; } |
说点什么