AcWing 316 .减操作

题目链接

大型补档计划

没想出来去看题解了。。。

关键是发现无论怎样括号嵌套，每个元素始终只有对答案的贡献为 + a[i] 或者 - a[i]。

而且第一个必然贡献是 +1，第二个必然是 -1。

所以用背包跑出来每个元素应该加还是减。

然后就是构造了。

观察到每个减操作实际上是把一个位置的贡献取反，而且这个位置不能是第一个位置。

随便来一个贡献序列

1 -1 1 1 -1 -1 1 -1 1 1 -1

最后一步一定是 a[1] - a[2]，所以此时的 a[2] 里的正负性一定和我们求出来的相反，所以就可以把每个 1 都减掉（除了 a[1]），最后变成了这种形式：

1 -1 -1 -1 -1 -1

这时候用 a[1] 把后面都减掉，之前被减掉的别的 1 相当于取反了两次，贡献是对的。

#include <iostream>

#include <cstring>

using namespace std;

const int N = 101, S = 10005 * 2, P = 10000;

int n, t, a[N], f[N][S], ans[N];

int main() {

	scanf("%d%d", &n, &t);

	for (int i = 1; i <= n; i++) scanf("%d", a + i);

	f[2][P + a[1] - a[2]] = -1;

	for (int i = 3; i <= n; i++)

		for (int j = 0; j < S; j++)

			if (f[i - 1][j]) {

				if(j + a[i] < S) f[i][j + a[i]] = 1;

				if(j - a[i] >= 0 )f[i][j - a[i]] = -1;

			}

	int s = t + P;

	for (int i = n; i > 1; i--) {

		if((ans[i] = f[i][s]) == 1) s -= a[i];

		else s += a[i];

	}

	int cnt = 0;

	for (int i = 2; i <= n; i++) if (ans[i] == 1) printf("%d\n", i - (cnt++) - 1);

    for (int i = n; i > 1; i--) if (ans[i] == -1) puts("1");

	return 0;

}

巴特西

AcWing 316 .减操作

最新文章

热门文章