|
题目描述 Description |
|
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。 |
|
输入描述 Input Description |
|
输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。 |
|
输出描述 Output Description |
|
输出文件paint.out包含一个整数，最多能正确粉刷的格子数。 |
|
样例输入 Sample Input |
|
3 6 3 |
|
样例输出 Sample Output |
|
16 |
|
数据范围及提示 Data Size & Hint |
|
30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。 |
之前的一些废话：过了一个非常愉快的暑假（去了欧洲，最后还临时在 杭州待了四天，爱奇艺充了一个月的会员，看了19部电影（《金刚狼1》《金刚狼2》《金刚狼3》《X战警1》《X战警2》《X战警3》《X战警第一战》《X战警逆转未来》《X战警天启》《战狼2》《摔跤吧！爸爸》《哈利波特与魔法石》《哈利波特与密室》《哈利波特与阿兹卡班的囚徒》《哈利波特与火焰杯》《哈利波特与凤凰社》《哈利波特与混血王子》《哈利波特与死亡圣器上》）《哈利波特与死亡圣器下》）可谓是浪上天了。所以得到的报应是开学考试继续炸。接下来的生活要步入正轨了！
题解：逐个分析每一行：设dp(i,j)表示到第i个格一共刷了j次，转移的话需要枚举 之前所有的k(0<=k<i),转移方程：dp(i,j)=max(dp(i,j),dp(i,k)+max(num1(k+1,i),num0(k+1,i))) num0(i,j)表示在(i,j)这些格之间数字0的数量，num1(i,j)类似，所以这个拿可以前缀和优化成O(n^4)。求完之后，我们设v(i,j)表示第i行刷j次的最大收益，转移为v(i,j)=dp(m,j)
之后问题就转化为了有一个容量为T的背包，有n组物品，每组有min(m,T)个物品可选，只能选一个，其中价值为v[i][j],重量是j。这个就可以进行DP来进行处理了。总复杂度O(n^4)
代码：
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; #define mem(a,b) memset(a,b,sizeof(a)) typedef pair<int,int> PII; #define X first #define Y second inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=55,maxt=2550; int n,m,t,dp[maxn][maxn],pre0[maxn],pre1[maxn],v[maxn][maxn],dp2[maxn][maxt];//v[i][j]表示第i行用j个最大代价 char s[maxn]; int main() { n=read();m=read();t=read(); for(int i=1;i<=n;i++) { scanf("%s",s+1); mem(pre0,0);mem(pre1,0);mem(dp,0); for(int j=1;j<=m;j++) { pre0[j]=pre0[j-1]+(s[j]=='0'); pre1[j]=pre1[j-1]+(s[j]=='1'); } //for(int j=1;j<=m;j++)printf("j:%d pre0:%d pre1:%d ",j,pre0[j],pre1[j]); for(int j=1;j<=m;j++) for(int k=1;k<=min(t,j);k++) for(int l=0;l<j;l++)dp[j][k]=max(dp[j][k],dp[l][k-1]+max(pre0[j]-pre0[l],pre1[j]-pre1[l])); for(int j=1;j<=min(m,t);j++)v[i][j]=dp[m][j]; //for(int j=1;j<=m;j++)for(int k=1;k<=min(t,j);k++)printf(" %d %d %d ",j,k,dp[j][k]); //for(int j=1;j<=min(m,t);j++)printf("%d: %d ",j,v[i][j]); }//有n组物品，每组有min(m,t)个物品可选，只能选一个，其中价值为v[i][j],重量是j,dp[i][j] for(int i=1;i<=n;i++) for(int j=1;j<=t;j++) for(int l=1;l<=min(m,j);l++) dp2[i][j]=max(dp2[i][j],dp2[i-1][j-l]+v[i][l]); printf("%d ",dp2[n][t]); return 0; }=
总结：好像没什么话要说