传送门：点我
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
6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..
11
2 5 1 1
#####
.....
5
Note
In the first test sample the picture after changing some colors can looks as follows:
.##..
.##..
.##..
.##..
.##..
.##..
题意：
给定n,m,x,y。之后输入n行m列的字符串数组，其中#表示黑色，. 表示白色。询问的是要让这个字符串数组，每[x,y]列是一个颜色，最少的更改次数。
看到题目猜一下是按列的DP，推了一下午结果鸽于发现初始状态写错了。
dp[i][0]表示第i列为.时候的最小费用
dp[i][1]表示第i列为#时候的最小费用
转移方程不难得到:
dp[i][0] = min(dp[i-j][1]+(p[i][0]-p[i-j][0]),dp[i][0]); 其中 x<= j <= y;
dp[i][1] = min(dp[i-j][0]+(p[i][1]-p[i-j][1]),dp[i][1]); 其中 x<= j <= y;
其中p为前缀和，即需要改变的次数，具体看代码。
这个方程的意思是：加上i这行，起码需要x行，最多y行，所以dp[i][k]是从dp[i-y][k]~dp[i-x][k]这一段更新上来,其中k=0或者1。
代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> using namespace std; char mp[1001][1001]; int p[1001][2]; int dp[1001][2]; int main(){ int n,m,x,y; memset(p,0,sizeof(p)); memset(dp,0x3f,sizeof(dp)); scanf("%d %d %d %d",&n,&m,&x,&y); for(int i = 0 ; i < n ; i++){ scanf("%s",mp[i]); } for(int i = 0 ; i < m ; i++){ for(int j = 0 ; j < n ;j ++){ if(mp[j][i] == '#'){ p[i+1][0]++; }else if(mp[j][i] == '.'){ p[i+1][1]++; } } } for(int i = 2; i <= m ; i ++){ p[i][0]+=p[i-1][0]; p[i][1]+=p[i-1][1]; } // dp[i][0]表示第i列为.时候的最小费用 // dp[i][1]表示第i列为#时候的最小费用 dp[0][0] = dp[0][1] = 0; for(int i = 1 ; i <= m ; i++){ for(int j = x ; j <= y && j <= i; j ++){ //加上i这行起码x行，最多y行，所以从dp[i-y]到dp[i-x]更新上来 dp[i][0] = min(dp[i-j][1]+(p[i][0]-p[i-j][0]),dp[i][0]); dp[i][1] = min(dp[i-j][0]+(p[i][1]-p[i-j][1]),dp[i][1]); } } printf("%d\n",min(dp[m][0],dp[m][1])); } /* 6 5 1 2 ##.#. .###. ###.. #...# .##.# ###.. */