CF225C Barcode 题解

fxttt · 2023-09-16 21:00:55 · 题解

CF225C Barcode 题解

思路

首先肯定要把矩阵转化成线性的，就是只存每一列转化成黑、白的代价（转化成黑的代价是白色的数量，白色同理）。

然后想到动归，如果正着动归（收集型）会很不方便，所以可以用扩散型。

举个例子，斐波那契额数列的式子是 f_i=f_{i-1}+f_{i-2}，可以写成 f_{i+1}=f_{i+1}+f_i 和 f_{i+2}=f_{i+2}+f_i 的形式。前者是收集型，后者是扩散型。

所以状态 f_{i,0/1} 表示从 1 到 i 列都满足条件，并且当前列颜色是黑或白的最少修改数。

那如何转移呢？

枚举从当前位置往后 x 到 y 之间的列数 j，将现在的位置到 i+j 的矩阵（已经化为区间）修改为同一颜色，也就是把整个图化为相邻颜色不同的矩阵。

得出转移方程：

其中 a 和 b 数组分别是每一列转成黑色和白色的代价的前缀和。

代码

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int b[1010];
int f[2010][2];
int main(){
    int n,m,x,y;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#'){
                b[j]++;
            }
            if(c=='.'){
                a[j]++;
            }
        }
    }
    for(int i=1;i<=m;i++){
        a[i]+=a[i-1];
        b[i]+=b[i-1];
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    f[0][1]=0;
    for(int i=0;i<m;i++){
        for(int j=x;i+j<=m && j<=y;j++){
            f[i+j][0]=min(f[i+j][0],f[i][1]+a[i+j]-a[i]);
            f[i+j][1]=min(f[i+j][1],f[i][0]+b[i+j]-b[i]);
        }
    }

    printf("%d",min(f[m][0],f[m][1]));
return 0;
}