题解：P9824 [ICPC 2020 Shanghai R] Fountains

Zelotz · 2025-07-18 10:50:57 · 题解

观察：固定选择的区间后，如何使总代价最小？把所有区间按 C 从大到小排序，按照这个顺序依次考虑它们会不会被选取。

这里我们说一个区间 [L,R] 的权值就是满足 L\leq l\leq r\leq R 且(l,r) 被选取者中 C(l,r) 最大值。

转化：于是先把所有区间从大到小排序，考虑 dp。

你发现此时我们只关心：第一，选取了多少个区间；第二，哪些 [L,R] 的权值已经固定：当我们确定 (l,r) 被选取后，所有满足 L\leq l\leq r\leq R 且还未确定权值的 [L,R] ，其权值就会确定。

设 dp_{i,k,S} 是考虑了前 i 个区间，当前选了 k 个区间，已知权值者状态为 S 时的最大总权值。

观察：发现，若 [L,i] 权值已知， [L,i+1] 权值一定也是已知的。如果我们令 a_L 是最小的 R 满足[L,R] 权值已知，那可以发现一件容易说明的事情：a 单调不降。

所有的 a 状态与 S 一一对应，于是 S 可以看成是 (0,0) 到 (n,n) 的一条路径上方的格子形成的集合，可能的 S 只有 \dbinom{2n}{n} 种。

预处理出状态 S 加入 (l,r) 后变成了哪个状态。复杂度 \mathcal O(n^4\dbinom{2n}n) 。也可以用 map。实际上我先写的 \mathcal O(n^5\dbinom{2n}n\log n) 直接过了，甚至没跑到 1s。

#define int ll
const int N = 10, P = 998244353;
typedef __int128 LL;
int n, a[N];

map <LL, int> dp[N * N][N * N];
struct itv {
    int l, r, x;
    bool operator < (const itv &t) const {
        return x > t.x;
    }
} arr[N * N];
int sum[N];
signed main() {
    cin >> n;
    R(i, 1, n) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int m = 0;
    R(i, 1, n) {
        int s = 0;
        R(j, i, n) {
            s += a[j];
            arr[++m] = {i, j, s};
        }
    }
    sort(arr + 1, arr + m + 1);

    dp[0][0][0] = 0;

    auto fill = [&](int i, int j, LL s, int val) {
        if (!dp[i][j].count(s)) {
            dp[i][j][s] = val;
        } else {
            dp[i][j][s] = max(dp[i][j][s], val);
        }
    } ;
    auto id = [&](int l, int r) {
        return (l - 1) * n + r;
    } ;
    LL all = 0; int alls = 0;
    R(l, 1, n) {
        R(r, l, n) {
            all |= (__int128(1) << id(l, r));
            alls += sum[r] - sum[l - 1];
        }
    }
    R(i, 0, m - 1) {
        R(j, 0, i) {
            for (auto [s, val] : dp[i][j]) {
                fill(i + 1, j, s, val);
                LL st = 0; int d = 0;
                R(l, 1, n) {
                    R(r, l, n) {
                        if (s >> id(l, r) & 1) {
                            st |= (__int128(1ll) << id(l, r));
                        } else if (l <= arr[i + 1].l && r >= arr[i + 1].r) {
                            st |= (__int128(1ll) << id(l, r));
                            d += sum[arr[i + 1].r] - sum[arr[i + 1].l - 1];
                        }
                    }
                }
//              assert((st & s) == s);
                fill(i + 1, j + 1, st, val + d);
            }
        }
    } 
    R(i, 1, m) {
        int mx = 0;
        for (auto [s, val] : dp[m][i]) {
            mx = max(mx, val);
        }
        cout << alls - mx << endl;
    }
    return 0;