原题链接
考察:线性dp
思路:
??想到了但三重循环以为会超时,实际是只有\(j=1\)时才有三重循环.
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n,m,x,y,cost[N][2],f[N][N][2];//0. 1#
char mp[N][N];
void solve()
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
if(mp[j][i]==‘#‘) cost[i][0]++;
else cost[i][1]++;
}
memset(f,0x3f,sizeof f);
f[0][0][0] = f[0][0][1] = 0;
for(int i=1;i<=m;i++)
for(int j=1;j<=y;j++)
{
f[i][j][0] = min(f[i-1][j-1][0]+cost[i][0],f[i][j][0]);
f[i][j][1] = min(f[i-1][j-1][1]+cost[i][1],f[i][j][1]);
if(j==1)
for(int k=x;k<=y;k++)
{
f[i][1][0] = min(f[i-1][k][1]+cost[i][0],f[i][1][0]);
f[i][1][1] = min(f[i-1][k][0]+cost[i][1],f[i][1][1]);
}
}
int ans = 0x3f3f3f3f;
for(int j=x;j<=y;j++)
for(int k=0;k<2;k++) ans = min(f[m][j][k],ans);
printf("%d\n",ans);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
solve();
return 0;
}