CF225C Barcode 题解
Moya_Rao
·
·
题解
题目大意
给定一个 n \times m 的矩阵，上面每个位置都涂了颜色。其中，. 表示白色，而 # 表示黑色。
现在要求你修改若干个位置，使得这个矩阵变成“条形矩阵”。
“条形矩阵”的定义：
- 每一列的颜色都要完全相同；
- 连续相同的列数不能低于 x，也不能超过 y。
请你求出最少要修改多少个位置才能使这个矩阵变成“条形矩阵”。
# 思路
首先一看到这种一列一列处理的，很容易想到把矩阵弄成那种一条一条的，分别统计一下每一列有多少个白色格子，又有多少个黑色格子。这里我们用 $a_i$ 表示第 $i$ 列有多少个白格子，用 $b_i$ 表示第 $i$ 列有多少个黑格子。顺便的，咱还得对 $a$ 和 $b$ 做个前缀和，方便后面统计。
然后很明显的，会想到动态规划。我们该怎么定义 $dp$ 数组呢？
简单简单，直接定义 $dp_{i,0/1}$ 表示当前考虑到前 $i$ 列，并且第 $i$ 列的颜色为白色或黑色时的最小修改次数。
定义出来了，那就再问个问题吧——答案是啥？问得好。答案的话，肯定不单单是 $dp_{m,0},$ 或者 $dp_{m,1}$ 而是 $\max(dp_{m,0},dp_{m,1})$。其实上很好想，对吧？
行，这些玩意儿都出来了，最重要的转移呢？咱们该如何转移？
很简单啦。我们可以枚举 $j$ 从 $x \sim y$，表示第 $i$ 列后面 $j$ 列的答案。是吧，已经看出来了，这个转移是扩散型！
那转移到底是啥？让我们来看看：
$$dp_{i+j,0}=\min(dp_{i+j,0},dp_{i,1}+a_{i+j}-a_i)$$
$$dp_{i+j,1}=\min(dp_{i+j,1},dp_{i,0}+b_{i+j}-b_i)$$
嘿嘿，很明了吧？
那这题是不是就解决了呢？差不多是了，但是别忘了一个很重要的点——初始化！没错没错，该如何初始化啊？简单着呢！我们首先让 $dp$ 数组的所有值都为无穷大，接着再将 $dp_{0,0}$ 与 $dp_{0,1}$ 的值赋为 $0$，就完事儿啦！
是不是还挺简单？那就赶紧开始写代码吧！顺便告诉你，代码贼短哦！
# 代码
代码很短，因此建议自己写，但我还是会放出来供大家参考。包对的，不信的话看这个[提交记录](https://codeforces.com/contest/225/submission/315800663)。不过大家可不要抄我的代码，那样毫无意义哦！
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,a[1005],b[1005],dp[1005][2];
int main(){
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;cin>>c;
if(c=='.')a[j]++;else b[j]++;
}
for(int i=1;i<=m;i++)a[i]+=a[i-1],b[i]+=b[i-1];
memset(dp,0x3f,sizeof(dp));dp[0][0]=0,dp[0][1]=0;
for(int i=0;i<m;i++)
for(int j=x;j<=y&&i+j<=m;j++){
dp[i+j][0]=min(dp[i+j][0],dp[i][1]+a[i+j]-a[i]);
dp[i+j][1]=min(dp[i+j][1],dp[i][0]+b[i+j]-b[i]);
}
cout<<min(dp[m][0],dp[m][1])<<"\n";
return 0;
}
```
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，万分感谢！