题解：P10811 【MX-S2-T2】排

· · 题解

观察一下性质，发现若是序列全为正数或全为负数或全为零，排序输出最大值即可。
接下来考虑序列中既有正数也有负数的情况。可以发现，此时序列中的零是无意义的，不论你放哪都不能造成影响，所以我们把它去掉，原因后面说。又根据题面中提供的式子，当前位为正的话，不能再叠加正数了，所以答案不会超过序列中的最大值。这时候就会考虑，除去最大值后的 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;
}