题意:
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次,他最多能正确粉刷多少格子?
一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。
解:先套路地设状态dp[i][j][k]为第 i 块木板,粉刷到第 j 个格子,用了k次刷子能刷对的最大个数。由于刷的时候和连不连起来有关,所以再加一维:dp[i][j][k][0/1],这一格刷0还是刷1,于是在这一块木板上有转移:
int now = s[i][j] - '0';
dp[i][j][k][0] = max(dp[i][j][k][0], dp[i][j - 1][k][0] + (now == 0));
dp[i][j][k][0] = max(dp[i][j][k][0], dp[i][j - 1][k - 1][1] + (now == 0));
dp[i][j][k][1] = max(dp[i][j][k][1], dp[i][j - 1][k][1] + (now == 1));
dp[i][j][k][1] = max(dp[i][j][k][1], dp[i][j - 1][k - 1][0] + (now == 1));
接下来考虑把木板连起来。因为中间可以空着不刷,所以不能直接接上一行的状态。现在题目转换为:已知每块木板被刷[0,t]次能刷对的格子数,现在最多刷t次,最多刷对几个格子。哎呀这不是背包嘛,粗粗一算n*t*t复杂度,有点高。再一思考长为m的木板最多刷m次就行了,n*m*t,很好,暴力转移即可。
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define maxx 105 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 998244353 int dp[55][55][2505][2]={0}; int dp1[55][55][2505]={0}; int dp2[2505]={0}; char s[55][55]={0}; signed main() { // int T; // scanf("%d",&T); // while(T--){ // // } int n, m, t; scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = 1; k <= t; k++) { int now = s[i][j] - '0'; dp[i][j][k][0] = max(dp[i][j][k][0], dp[i][j - 1][k][0] + (now == 0)); dp[i][j][k][0] = max(dp[i][j][k][0], dp[i][j - 1][k - 1][1] + (now == 0)); dp[i][j][k][1] = max(dp[i][j][k][1], dp[i][j - 1][k][1] + (now == 1)); dp[i][j][k][1] = max(dp[i][j][k][1], dp[i][j - 1][k - 1][0] + (now == 1)); dp1[i][j][k] = max(dp[i][j][k][0], dp[i][j][k][1]); } } } for (int i = 1; i <= n; i++) { for (int k = t; k > 0; k--) { for (int j = 0; j <= min(k, m); j++) { dp2[k] = max(dp2[k], dp2[k - j] + dp1[i][m][j]); } } } printf("%d\n", dp2[t]); return 0; }View Code
标签:格子,int,粉刷,55,SCOI2009,P4158,dp,define From: https://www.cnblogs.com/capterlliar/p/16811184.html