『算法-ACM 竞赛-CodeForces』 225C. Barcode(DP)

C. Barcode

Desciption

You’ve got an n × m pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.

A picture is a barcode if the following conditions are fulfilled:

All pixels in each column are of the same color.
The width of each monochrome vertical line is at least x and at most y pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than x or greater than y.
Input

The first line contains four space-separated integers n, m, x and y (1 ≤ n, m, x, y ≤ 1000; x ≤ y).

Then follow n lines, describing the original image. Each of these lines contains exactly m characters. Character “.” represents a white pixel and “#” represents a black pixel. The picture description doesn’t have any other characters besides “.” and “#”.

Output

In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.

Examples

input
6 5 1 2
##.#.
.###.
###..
#…#
.##.#
###..
output
11
input
2 5 1 1

…..
output
5
Note
In the first test sample the picture after changing some colors can looks as follows:

.##..
.##..
.##..
.##..
.##..
.##..
In the second test sample the picture after changing some colors can looks as follows:

.#.#.
.#.#.
————————-****——————-

先把每列修改的数量保存下来，都变成#的花费，和都变成‘ . ’的花费，这样状态就变成了第 i 列，就变成一个普通 DP 题。
这道题思考起来没有那没有那么复杂，讨论第 i 列染或不染（变成#或不变）但是无论染或不染都要至少染或不然连续的 X 以上，且不可超过 Y 列，那么就是说当换状态时如果变成另一种状态一定是从另一种状态的连续的 x 到 Y 列变化而来，而不改变状态时就是连续的一种状态，累加当前状态的消耗。进而得到状态转移方程

for(int k=x;k<=y;k++){
	dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][1]+cnt[i][0]);
	dp[i][j][1]=min(dp[i][j][1],dp[i-1][k][0]+cnt[i][1]);
}

进而可得出代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005;
const int INF=0x3f3f3f3f;
int a[maxn][maxn];
int cnt[maxn][2];
int dp[maxn][maxn][2];
char c[maxn][maxn];
int main()
{
    int m,n,x,y;
    scanf(" %d %d %d %d ",&m,&n,&x,&y);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            char x;
            scanf(" %c",&x);
            if(x=='#')cnt[j][1]++;
            else cnt[j][0]++;
        }
    }
    memset(dp,0x3f,sizeof(dp));
   for(int i=0;i<n;i++)
   {
        if(i==0) for(int k=0;k<2;k++) {
            dp[i][1][k]=cnt[i][k];
            continue;
        }
        for(int j=1;j<=i+1&&j<=y;j++)
        {
            if(j==1)
            {
                for(int k=x;k<=y;k++){
                    dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][1]+cnt[i][0]);
                    dp[i][j][1]=min(dp[i][j][1],dp[i-1][k][0]+cnt[i][1]);
                }
            }
            else {
                dp[i][j][0]=dp[i-1][j-1][0]+cnt[i][0];
                dp[i][j][1]=dp[i-1][j-1][1]+cnt[i][1];
            }
        }
    }
    int ans=INF;
    for(int i=x;i<=y;i++)
    {
        ans=min(ans,dp[n-1][i][0]);
        ans=min(ans,dp[n-1][i][1]);
    }
    cout<<ans<<endl;
}

这个代码我调了三个小时，写出来之后！不知道为什么前边用 cin 输入这个题就过不了，而且每组样例都能本地 AC。尴尬，求解？