就是按照 % 体积的余数来分组，每组单调队列优化。

直接上模板好了。

1 #include 
      
        2  3 typedef long long LL; 4 const int N = 100010; 5  6 int n, V, cnt[N], cost[N]; 7 LL f[2][N], val[N], p[N], top, head; 8  9 inline void Max(LL &a, const LL &b) {10     a < b ? a = b : 0;11     return;12 }13 14 int main() {15 16     freopen("bag.in", "r", stdin);17     freopen("bag.out", "w", stdout);18 19     scanf("%d%d", &n, &V);20     for(int i = 1; i <= n; i++) {21         scanf("%d%d%lld", &cnt[i], &cost[i], &val[i]);22     }23     LL ans = 0;24     for(int i = 1; i <= n; i++) {25         for(int j = 0; j < cost[i]; j++) {26             p[head = top = 1] = 0;27             for(int g = 1; g * cost[i] + j <= V; g++) {28                 while(g - p[head] > cnt[i]) head++;29                 int t = p[head];30                 Max(f[i & 1][g * cost[i] + j], f[(i - 1) & 1][t * cost[i] + j] + (g - t) * val[i]);31                 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]) {32                     top--;33                 }34                 p[++top] = g;35             }36         }37         for(int j = 0; j <= V; j++) {38             Max(ans, f[i & 1][j]);39             f[(i - 1) & 1][j] = f[i & 1][j];40         }41     }42     43     printf("%lld\n", ans);44     return 0;45 }46 /*47 5 5048 1 1 749 2 1 450 2 4 151 3 1 352 2 3 853 -------------- 4254 */