MnZn袜子刚学OI 1s，简单线性 dp 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,w[1001],b[1001];
int f[1001][1001][3];
string s[1001];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;++i){
		cin>>s[i];
	}
	for(int j=0;j<m;++j){
		for(int i=1;i<=n;++i){
			if(s[i][j]=='#'){
				w[j+1]++;
			}
			if(s[i][j]=='.'){
				b[j+1]++;
			}
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=y;++j){
			f[i][j][0]=2e9;
			f[i][j][1]=2e9;
		}
	}
	f[1][1][1]=b[1];
	f[1][1][0]=w[1];
	for(int i=2;i<=m;++i){
		for(int j=x;j<=y&&j<=i;++j){
			f[i][1][1]=min(f[i][1][1],f[i-1][j][0]+b[i]);
			f[i][1][0]=min(f[i][1][1],f[i-1][j][1]+w[i]);
		}
		for(int j=2;j<=y&&j<=i;++j){
			f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+b[i]);
			f[i][j][0]=min(f[i][j][0],f[i-1][j-1][0]+w[i]);
		}
	}
	int ans=2e9;
	for(int j=x;j<=y;++j){
		ans=min(ans,f[m][j][1]);
		ans=min(ans,f[m][j][0]);
	}
	cout<<ans<<endl;
	return 0;
}