点我写题  

题目描述

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

思路

一开始我是觉得对每行的连续段做一次01背包，但是忽略了能错误粉刷的情况，于是很自然的想知道每行粉刷若干次的最优值，引出另一个问题，用ycl[i][j]表示当前行的前i个，刷j次的最优粉刷情况，转移就是考虑最后一次刷了多远即可，最后一次的贡献是该次粉刷包含的01元素个数取最大值。然后用分组背包的思路去更新我的答案dp即可。

代码

java">import java.util.*;
import java.io.*;
public class Main{public static void main(String[] args)throws Exception{BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));BufferedWriter wd=new BufferedWriter(new OutputStreamWriter(System.out));String dr[]=rd.readLine().split(" ");int n=Integer.parseInt(dr[0]),m=Integer.parseInt(dr[1]),T=Integer.parseInt(dr[2]);int dp[]=new int [T+10];for(int i=0;i<T+10;i++) dp[i]=-(int)1e9;dp[0]=0;int sum0[]=new int [m+10];int sum1[]=new int [m+10];for(int i=1;i<=n;i++) {String s=" "+rd.readLine();sum0[0]=sum1[0]=0;for(int j=1;j<=m;j++) {sum0[j]=sum0[j-1];sum1[j]=sum1[j-1];if(s.charAt(j)=='1') sum1[j]++;else sum0[j]++;}int ycl[][]=new int [m+10][Math.min(m, T)+10];for(int j=1;j<=m;j++) {for(int k=1;k<=Math.min(T,j);k++) {for(int p=j-1;p>=0;p--) {int mx=Math.max(sum1[j]-sum1[p], sum0[j]-sum0[p]);ycl[j][k]=Math.max(ycl[j][k],ycl[p][k-1]+mx);}}}for(int j=T;j>=1;j--) {for(int p=Math.min(j, m);p>=1;p--) {dp[j]=Math.max(dp[j],dp[j-p]+ycl[m][p]);}}}wd.write(dp[T]+"\n");wd.flush();}}