题目链接：http://codeforces.com/problemset/problem/225/C
题目大意：给你一个矩阵，矩阵中只有＃和.两种符号。现在我们希望能够得到一个新的矩阵，新的矩阵满足每一列都只有一种符号，并且连续相同符号的列数在区间[x,y]之间。
解：
现将列中的点统计出来，然后就是枚举把列数在x到y之间的需要更改为点的统计出来。这些点染上白色。
然后再将列数在x到y之间的需要更改为井号的点数统计出来，这些点染成黑色。
接下来就是DAG上的动态规划了，dp[i]代表从i到终点的最短路径。路径要求：相邻两个点的颜色不相同。
我是用的记忆化搜索，当然也很好改成递推。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cmath>
#include <numeric>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <functional>
#include <queue>
#include <stack>
#include <string>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ size()
#define ST begin()
#define ED end()
#define CLR clear()
#define ZERO(x) memset((x),0,sizeof(x))
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double EPS = 1e-;
const int INF = ;
const int MAX_N = ;
struct NODE{
int l,r,val;
}; vector<NODE> vec[MAX_N][];
int n,m,x,y;
int a[MAX_N],sum[MAX_N],sumn[MAX_N];
int dp[MAX_N][]; int f(int st,int type){
int res = INF;
if( dp[st][type]!=INF ){
return dp[st][type];
}
for(int j=;j<vec[st][type].size();j++){
if(vec[st][type][j].r==m)
res = min(res,vec[st][type][j].val);
}
for(int j=;j<vec[st][type].size();j++) {
if(vec[st][type][j].r!=m)
res = min(res,vec[st][type][j].val+f(vec[st][type][j].r+,-type));
}
return dp[st][type] = res;
} int main(){
scanf("%d%d%d%d",&n,&m,&x,&y);
ZERO(a);
for(int i=;i<=n;i++){
getchar();
for(int j=;j<=m;j++){
char c = getchar();
if( c=='.' ){
a[j]++;
}
}
} for(int i=;i<=m;i++){
sum[i] = sum[i-]+a[i];
sumn[i] = sumn[i-]+n-a[i];
//dp[i] = INF;
} for(int i=;i<=m;i++){
for(int j=x;j<=y;j++){
NODE N;
N.l = i;
N.r = i+j-;
if( N.r>m ) break;
N.val = sum[N.r] - sum[N.l-];
vec[N.l][].PB(N);
N.val = sumn[N.r] - sumn[N.l-];
vec[N.l][].PB(N);
}
}
for(int i=;i<MAX_N;i++){
dp[i][] = dp[i][] = INF;
}
int ans = f(,);
//for(int i=1;i<=m;i++) printf("%d ",dp[i]); puts("");
//for(int i=1;i<=m;i++) dp[i] = INF;
ans = min(ans,f(,));
//for(int i=1;i<=m;i++) printf("%d ",dp[i]); puts("");
printf("%d\n",ans);
return ;
}