粉刷匠

【问题描述】

windy有 N 条木板需要被粉刷。

每条木板被分为 M 个格子。

每个格子要被刷成红色或蓝色。

windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。

每个格子最多只能被粉刷一次。

如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

【输入格式】

输入文件paint.in{dy}行包含三个整数，N M T。

接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

【输出格式】

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

【输入样例】

3 6 3

111111

000000

001100

【输出样例】

16

【数据规模和约定】

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。

{bfb}的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

opt[i,j]（前i个木板刷j次的{zy}值）:=opt[i-1,k]+wood[i,j-k]（第i个木板刷j-k次);

f[i,j](求第X块木板前j个格子刷i次的{zy}值，{zh1}处理到wood数组中)：=f[i-1,k]+w[k+1,j](区间k+1到j刷一次的{zy}值，枚举{zh1}一刷！！)

务必注意枚举范围！

for i:=1 to m do
    for j:=1 to m do
      begin
        for k:=i-1 to j-1 do
          begin
            if f[i-1,k]+max(blue[j]-blue[k],red[j]-red[k])>f[i,j] then
              f[i,j]:=f[i-1,k]+max(blue[j]-blue[k],red[j]-red[k]);
          end;
      end;

for i:=0 to t do
    wood[x,i]:=f[i,m];

for i:=1 to n do
    for j:=1 to i*m do
      begin
        for k:=0 to j do
          begin
            if opt[i-1,j-k]+wood[i,k]>opt[i,j] then opt[i,j]:=opt[i-1,j-k]+wood[i,k]
          end;
      end;

由于本题的特殊性，我们还可以加以优化（是RCX神牛教我的，一个常数优化）

我们刷一个格子不如把一个连续的区间刷完，所以可以把一段相同的格子压缩成一个

同样注意枚举范围

for i:=1 to num[x] （第x块木板有多少个色条）do
    for j:=1 to min(t,i) do
      begin
        for k:=j-1 to i do
          if f[k,j-1]+max(sum1[x,i]-sum1[x,k],sum2[x,i]-sum2[x,k])>f[i,j] then
            f[i,j]:=f[k,j-1]+max(sum1[x,i]-sum1[x,k],sum2[x,i]-sum2[x,k]);
      end;

for i:=1 to t do

     wood[x,i]:=f[num[x],i];

for i:=1 to n do
    for j:=1 to t do
      begin
        for k:=0 to min(j,num[i]) do
          if wood[i,k]+opt[i-1,j-k]>opt[i,j] then
            opt[i,j]:=wood[i,k]+opt[i-1,j-k];
      end;