JZOJ 1035. 【SCOI2009】粉刷匠

题目

Description

windy有 N 条木板需要被粉刷。
每条木板被分为 M 个格子。
每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。
每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

 

Input

第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

Output

输出一个整数，表示最多能正确粉刷的格子数。

 

Sample Input

3 6 3
111111
000000
001100

Sample Output

16

 

Data Constraint

 

 

Hint

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

分析

 

• 设f[i][j][0/1]为前i个格子刷了j次，当前第i格的颜色为0/1
• 显然

  r=((i-1)*m)+j;
  			if (j!=1)
  			f[r][k][0]=max(f[r-1][k][0],f[r-1][k-1][1]),
  			f[r][k][1]=max(f[r-1][k][1],f[r-1][k-1][0]);
  			else 
  			f[r][k][0]=max(f[r-1][k-1][0],f[r-1][k-1][1]),
  			f[r][k][1]=max(f[r-1][k-1][1],f[r-1][k-1][0]);
  			if (s[j-1]=='0') f[r][k][0]++;
  			else f[r][k][1]++;

 

代码

#include <iostream>
using namespace std;
int f[2501][2501][2],r;  
int main()
{
    int n,m,t;
    cin>>n>>m>>t;
    string s;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        for (int j=1;j<=m;j++)
          for (int k=1;k<=t;k++)
        {
            r=((i-1)*m)+j;
            if (j!=1)
            f[r][k][0]=max(f[r-1][k][0],f[r-1][k-1][1]),
            f[r][k][1]=max(f[r-1][k][1],f[r-1][k-1][0]);
            else 
            f[r][k][0]=max(f[r-1][k-1][0],f[r-1][k-1][1]),
            f[r][k][1]=max(f[r-1][k-1][1],f[r-1][k-1][0]);
            if (s[j-1]=='0') f[r][k][0]++;
            else f[r][k][1]++;
            
        }
    }
    cout<<max(f[r][t][1],f[r][t][0]);
}