题解：AT_agc045_c [AGC045C] Range Set

要去想怎么判断一个字符串能不能涂出来，可以贪心判断，有三个变量

x,p,q

，初始

x=0,p=A,q=B

，然后每次如果：

字符是 0
- 如果 $x=0$ ，或者 $p=0$ ，那么 p--,q--；
- 否则，p--，然后 q=B-1。
字符是 1 同理。
如果 $p<0$ ，p=0；如果 $q<0$ ，q=0。
把 $x$ 改成现在的字符。

枚举的暴力代码如下：

CPP

int answer = 0;
for (int S = 0; S < 1 << n; S ++) {
	int x = 0, p = A, q = B;
	for (int i = 1; i <= n; i ++) {
		int v = (S >> (i - 1) & 1);
		if (v) {
			if (x || !p) p = max(p - 1, 0), q = max(q - 1, 0);
			else p = max(p - 1, 0), q = B - 1;
		} else {
			if (!x || !q) p = max(p - 1, 0), q = max(q - 1, 0);
			else q = max(q - 1, 0), p = A - 1;
		}
		x = v;
	}
	if (!p && !q) {
		answer ++;
	}
}

然后就可以把

x,p,q

全部用动态规划的状态记录（第一维

p

，第二维

q

，第三维

x

），用一个滚动数组，dp1 是当前的,dp2 是下一个。转移方程式非常简单的，这都不知道可以不做这题了。有下面的代码：

CPP

for (int i = 1; i <= n; i ++) {
	dp2[0][0][0] += dp1[0][0][0] + dp1[0][0][1];
	dp2[0][0][1] += dp1[0][0][0] + dp1[0][0][1];
	for (int x = 1; x <= A; x ++) {
		dp2[x - 1][0][0] += dp1[x][0][0];
		dp2[x - 1][0][1] += dp1[x][0][1];
		dp2[x - 1][B - 1][1] += dp1[x][0][0];
		dp2[x - 1][0][0] += dp1[x][0][1];
	}
	for (int y = 1; y <= B; y ++) {
		dp2[0][y - 1][0] += dp1[0][y][0];
		dp2[0][y - 1][1] += dp1[0][y][1];
		dp2[0][y - 1][1] += dp1[0][y][0];
		dp2[A - 1][y - 1][0] += dp1[0][y][1];
	}
	for (int x = 1; x <= A; x ++) for (int y = 1; y <= B; y ++) {
		dp2[x - 1][y - 1][0] += dp1[x][y][0];
		dp2[x - 1][y - 1][1] += dp1[x][y][1];
		dp2[x - 1][B - 1][1] += dp1[x][y][0];
		dp2[A - 1][y - 1][0] += dp1[x][y][1];
	}
	for (int x = 0; x <= A; x ++) for (int y = 0; y <= B; y ++) {
		dp1[x][y][0] = dp2[x][y][0], dp1[x][y][1] = dp2[x][y][1];
		dp2[x][y][0] = dp2[x][y][1] = 0;
	}
}

这样的时间复杂度是

O(n^3)

。

要维护矩阵每次向左下角移动，维护每行每列的和就可以了。优化之后时间复杂度变成

O(n^2)

。

题解：AT_agc045_c [AGC045C] Range Set

文章操作

相关推荐

评论

题解：AT_agc045_c [AGC045C] Range Set