「解题报告」CF1442D Sum

首先可以发现，如果我们选了两堆且两堆均没选完，那么如果我们将较小的一个改成选较大的一个的下一个，这样一直选一定是更优的，最后肯定会使一些堆全部选完，一些堆没选，一个堆选了一部分。

考虑枚举选了一部分的那一堆，然后将其它堆看作一个物品做背包。这样同一个物品被加了狠多次，我们考虑分治，每次在一层上将某一半加进去，再递归到另一半（有点类似于线段树分治），这样复杂度就变成了 \(O(nk \log n)\)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
int n, k;
vector<long long> a[MAXN];
long long sum[MAXN];
int len[MAXN];
long long f[30][MAXN];
long long ans = 0;
long long tmp[MAXN];
void solve(int l, int r, int cnt) {
    if (l == r) {
        cnt--;
        tmp[0] = f[cnt][0];
        for (int i = 1; i <= k; i++) {
            tmp[i] = max(tmp[i - 1], f[cnt][i]);
        }
        long long pre = 0;
        for (int i = 0; i <= min(k, len[l]); i++) {
            if (i) pre += a[l][i - 1];
            ans = max(ans, tmp[k - i] + pre);
        }
        return;
    }
    int mid = (l + r) >> 1;
    for (int i = 0; i <= k; i++) f[cnt][i] = f[cnt - 1][i];
    for (int i = mid + 1; i <= r; i++) {
        for (int j = k; j >= len[i]; j--) {
            f[cnt][j] = max(f[cnt][j], f[cnt][j - len[i]] + sum[i]);
        }
    }
    solve(l, mid, cnt + 1);
    for (int i = 0; i <= k; i++) f[cnt][i] = f[cnt - 1][i];
    for (int i = l; i <= mid; i++) {
        for (int j = k; j >= len[i]; j--) {
            f[cnt][j] = max(f[cnt][j], f[cnt][j - len[i]] + sum[i]);
        }
    }
    solve(mid + 1, r, cnt + 1);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &len[i]);
        for (int j = 1; j <= len[i]; j++) {
            int b; scanf("%d", &b);
            a[i].push_back(b);
            sum[i] += b;
        }
    }
    memset(f, 0xef, sizeof f);
    f[0][0] = 0;
    solve(1, n, 1);
    printf("%lld\n", ans);
    return 0;
}