【MX-S2-T2】 排 练习笔记

lzh0613 · 2026-10-22 00:48:53 · 题解

挺好的 DP 题。

先特判掉 3 种特殊情况。

然后发现 0 对整个答案没有任何贡献，可以去掉。剩下的就是有正有负的情况了。

可以发现对于所有的 a 的重排，f_n \le \max\limits_{1 \le i \le n} a_i，证明如下。

:::info[稍微繁琐加不严谨的证明] 易得 f_0 = 0 \le \max\limits_{1 \le i \le n} a_i，假设 f_{i - 1} \le \max\limits_{1 \le i \le n} a_i，只需证明 f_i \le \max\limits_{1 \le i \le n} a_i，可以分 2 类情况。

2. - $a_i > 0$，那么条件 $f_{i - 1} \times a_i \le 0$ 等价于 $f_{i - 1} < 0$，于是 $f_i = f_{i - 1} \times a_i \le a_i \le \max\limits_{1 \le i \le n} a_i$。 - $a_i < 0$，那么 $f_i = f_{i - 1} \times a_i < f_{i - 1} \le \max\limits_{1 \le i \le n} a_i$。 :::

那么最优答案一定是 \max\limits_{1 \le i \le n} a_i + x，其中 x 是我们需要求的数，且 x \le 0。

可以发现对于 a 选择子集只要选出的子集和 sum \le 0 就一定有一种构造顺序使得这些被选中的数真正贡献到 x 中而没被选中的数则不会有效贡献，一种构造如下。

:::info[一种构造]

1. 从选出的负数中取一个放在最前面。
2. 放所有没选出的负数在后面。
3. 放选出的所有不包括 \max\limits_{1 \le i \le n} a_i 的正数和剩下的选出的负数在后面。
4. 放 \max\limits_{1 \le i \le n} a_i。

5. 放未选出的正数。

然后就发现这就是裸的背包 DP，看算法标签发现可以用 bitset 卡常，bitset 可以开大一点。

#include <bits/stdc++.h>
#define y0 sto_czx35_orz//防 CE
using namespace std;
const int N = 2e3 + 5, x = (N * N) >> 1; 
int n, a[N], ans;
bool ff = true, fz = true, f0 = true;
bitset<N * N> dp;  
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) {
            i--, n--; continue;
        }
        else f0 = false;
        if (a[i] >= 0) ff = false;
        if (a[i] <= 0) fz = false;
    }
    sort(a + 1, a + n + 1);
    if (f0) {cout << 0; return 0;}
    if (ff || fz) {cout << a[n]; return 0;}
    for (int i = 1; i < n; i++) {
        if (a[i] > 0) dp |= (dp << a[i]);
        else dp |= (dp >> (-a[i]));
        dp[x + a[i]] = true;
    }
    for (int i = 0; i > -N; i--) {
        if (dp[x + i]) {
            cout << i + a[n];
            break;
        }
    }
    return 0;
}