网站建设与维护心得体会,邓州企业网站,网站群建设公司排行榜6,昆明官渡区网站建设链接#xff1a;
题目描述 windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷#xff0c;只能选择一条木板上一段连续的格子#xff0c;然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次#…链接
题目描述 windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷只能选择一条木板上一段连续的格子然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次他最多能正确粉刷多少格子 一个格子如果未被粉刷或者被粉刷错颜色就算错误粉刷。 输入描述: 输入文件paint.in第一行包含三个整数N M T。 接下来有N行每行一个长度为M的字符串0’表示红色1’表示蓝色。 输出描述: 输出文件paint.out包含一个整数最多能正确粉刷的格子数。 示例1 输入
3 6 3
111111
000000
001100输出
16题意
n个木板有m个格子能粉刷t次每次可以粉刷连续的一段问最多能正确粉刷多少个格子
题解
怎么涂才最大化其实全涂最好为什么?反正涂错没惩罚涂对就算赚但是我们只能涂t次所以就是t行涂满 dp的做法 有二维dp和四维dp的做法
二维dp
就是一个分组背包求解 预处理每块木板的最优解 因为木板只有0或1所以我们将1统计出来剩下的就是0 可以用到前缀和来统计1的数量 pre[i]表示前i块中1的数量 dp [ i ] [ j ] 表示前i块木板粉刷j次最多可以刷的格子数
我们根据题意可以得到转移方程 preepre[r]-pre[l]//表示区间l到r之间1的数量 f [ r] [ j ] max ( f [ r ] [ j ] [ , f [ l ] [ j-1 ] max ( pree ,r-l-pree)) 怎么理解 前r块的木板粉刷j次是前l块木板粉刷j-1次再加上l与r之间的最大数这个最大数是指1和0哪个出现的次数最多这样就粉刷数量多的那个颜色
代码略
四维dp
dp [ i ] [ j ] [ k ] [ 1 / 0] 表示前i条第j段涂了k次涂成红0或蓝1的最多格子数
如果涂的是当前木板第一段也就是j1就要接着上一个木板转移 dp[i][j][k][0]if(a[i][j]′0 ′)max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1]) 第i块木板的第一段是由当前木板的颜色加上上块木板的最大值情况 dp[i][j][k][1] if(a[i][j] ‘1’)max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1])
如果不是当前木板第一段那就是同块木板的上一段承接而来 dp[i][j][k][0]if(a[i][j] ′0′ ) max(dp[i][j−1][k][0],dp[i][j−1][k−1][1])
dp[i][j][k][1] if(a[i][j] ’ 1 ) max(dp[i][j-1][k-1][0],dp[i][j-1][k][1]) 本段木板颜色直接承接前一段的最大值 答案就是看红0或蓝1哪个最多 dp[n][m][t][0/1] 看到一个大佬用的滚动数组压维秒啊
滚动数组压维版代码 for (int i 1; i n; i)for (int j 1; j m; j)for (int k 1; k t; k){if (j 1)dp[i 1][j][k][1] max(dp[(i - 1) 1][m][k - 1][0], dp[(i - 1) 1][m][k - 1][1]) (a[i][j] 1 0);elsedp[i 1][j][k][1] max(dp[i 1][j - 1][k][1], dp[i 1][j - 1][k - 1][1 ^ 1]) (a[i][j] 1 0);if (j 1)dp[i 1][j][k][0] max(dp[(i - 1) 1][m][k - 1][0], dp[(i - 1) 1][m][k - 1][1]) (a[i][j] 0 0);elsedp[i 1][j][k][0] max(dp[i 1][j - 1][k][0], dp[i 1][j - 1][k - 1][0 ^ 1]) (a[i][j] 0 0);}
