CF225C Barcode
Autream
·
·
题解
容易发现字符是如何在矩阵中分配的与答案无关，实际上只需要处理列与列之间的关系。
于是可以将问题抽象为：将一个长度为 m 的序列染成两种颜色，代价已知，且染色后的序列连续相同颜色的长度必须在 [x,y] 中，求最小代价。
问题转换为线性，染色的代价是显然的。
考虑 DP。
设 dp_{i, 1/0, j} 表示将第 i 位染成 1/0，到这一位已经连续 j 个颜色相同的最小代价。
状态转移方程：
\begin{cases}
dp_{i, c, 1} = \min \limits _{j = x} ^y dis + dp_{i - 1, c \oplus 1, j} \\
dp_{i, c, j \in[2, y] = dis + dp_{i - 1, c, j - 1}}
\end{cases}
## 代码
```cpp
CI N = 1e3 + 5;
int n, m, x, y, ans = 1e9, dp[N][2][N], dis[2][N];
char ch[N][N];
signed main() {
n = read(), m = read(), x = read(), y = read();
rep(j, 1, n) arrin(ch[j], m + 1);
rep(j, 1, m) rep(i, 1, n) dis[0][j] += ch[i][j] == '.', dis[1][j] += ch[i][j] == '#';
mem(dp, 0x3f);
dp[1][0][1] = dis[0][1], dp[1][1][1] = dis[1][1];
rep(i, 2, m) rep(c, 0, 1) {
rep(j, x, y) dp[i][c][1] = std::min(dp[i][c][1], dis[c][i] + dp[i - 1][!c][j]);
rep(j, 2, y) dp[i][c][j] = dis[c][i] + dp[i - 1][c][j - 1];
}
rep(i, x, y) ans = std::min({ ans, dp[m][0][i], dp[m][1][i] });
print(ans);
return 0;
}
```