CF225C Barcode

容易发现字符是如何在矩阵中分配的与答案无关，实际上只需要处理列与列之间的关系。

于是可以将问题抽象为：将一个长度为

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}

n,m,x,y

同阶，时间复杂度

O(n ^ 2)

。

代码

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;
}

文章操作

代码

相关推荐

评论

CF225C Barcode