單調隊列優化多重背包

就是按照 % 體積的余數來分組，每組單調隊列優化。

直接上模板好了。

#include <bits/stdc++.h>

typedef long long LL;
const int N = 100010;

int n, V, cnt[N], cost[N];
LL f[2][N], val[N], p[N], top, head;

inline void Max(LL &a, const LL &b) {
    a < b ? a = b : 0;
    return;
}

int main() {

    freopen("bag.in", "r", stdin);
    freopen("bag.out", "w", stdout);

    scanf("%d%d", &n, &V);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%lld", &cnt[i], &cost[i], &val[i]);
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < cost[i]; j++) {
            p[head = top = 1] = 0;
            for(int g = 1; g * cost[i] + j <= V; g++) {
                while(g - p[head] > cnt[i]) head++;
                int t = p[head];
                Max(f[i & 1][g * cost[i] + j], f[(i - 1) & 1][t * cost[i] + j] + (g - t) * val[i]);
                while(top >= head && f[(i - 1) & 1][cost[i] * p[top] + j] + (g - p[top]) * val[i] <= f[(i - 1) & 1][g * cost[i] + j]) {
                    top--;
                }
                p[++top] = g;
            }
        }
        for(int j = 0; j <= V; j++) {
            Max(ans, f[i & 1][j]);
            f[(i - 1) & 1][j] = f[i & 1][j];
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}
/*
5 50
1 1 7
2 1 4
2 4 1
3 1 3
2 3 8
-------------- 42
*/

?