自动搬运

查看原文

来自洛谷，原作者为

	silhouettel reality

搬运于2025-08-24 23:01:30，当前版本为作者最后更新于2024-07-28 15:01:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观察一下性质，发现若是序列全为正数或全为负数或全为零，排序输出最大值即可。
接下来考虑序列中既有正数也有负数的情况。可以发现，此时序列中的零是无意义的，不论你放哪都不能造成影响，所以我们把它去掉，原因后面说。又根据题面中提供的式子，当前位为正的话，不能再叠加正数了，所以答案不会超过序列中的最大值。这时候就会考虑，除去最大值后的 $n - 1$ 个数，它们构成的重排的和在不超过零的情况下，显然是越大越优秀的。大于零没有意义，因为它不会作为答案。这很像是背包问题，询问能否找到一种填数方式。一看值域很小，思路大抵是对的，那么就要判断题面式子是否有相对应的性质，即我们是否可以随心所欲地选取我们想要的数。这里给出构造，将被选择的负数的其中之一放在开头，后面一段接着所有未选择的负数，然后把剩下被选择的正数（除去最大值）和被选择的负数按某种顺序排列使它们都被算入贡献，（因为它们最终的和是小于等于零的，所以我们一定可以得到一个将所有数都用上的排列顺序），再把最大值接上，最后让剩下未被选择的正数堆在尾部就行。那么这确实是一个背包问题，可以用 bitset 优化复杂度，不详细说。
解释一下去零的问题，由于至少一个非零数会被选，所以那 $n - 1$ 个数构成的重排的和不可以只由单个零产生，若是不把零去掉，就无法判断和为零的方案到底是多个数组合出来的，还是只选了一个零。
bitset 只要开 $4 \times 10^6$ 级别就行，因为当一方（正数或负数）的和超过了 $2 \times 10^6$，那么它不可能对答案有贡献。若想产生贡献，就需要另一方的和至少有 $2 \times 10^6$，这是无法实现的。

#include <bits/stdc++.h>
using namespace std;
#define real signed
#define enl '\n'

const int iinf = 0x3f3f3f3f;
const int st = 2000001;
int n;
int a[2011];
vector<int> se;
bitset<4000011> f;

real main() {
	std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++)
		if (a[i]) se.push_back(a[i]);
	sort(se.begin(), se.end());
	bool flg = true;
	for (int i = 1; i <= n; i++)
		if (a[i] * a[1] < 0) flg = false;
	if (se.empty()) cout << 0;
	else if (flg) cout << se[se.size() - 1];
	else  {
		for (int i = 0; i < se.size() - 1; i++) {
			if (se[i] > 0) f |= f << se[i];
			else f |= f >> -se[i];
			f[st + se[i]] = 1;
		}
		int ma = -iinf;
		for (int i = st - 2000; i <= st; i++)
			if (f[i]) ma = i;
		cout << ma - st + se[se.size() - 1];
	}
    return 0;
}