1. #pragma GCC optimize(2)
    3. #include <iostream>
    4. #include <functional>
    5. #include <algorithm>
    6. #include <vector>
    7. #include <deque>
    8. #include <stdlib.h>
    9. #include <string.h>
    10. using namespace std;
    12. class Solver {
    13.     // 野路子
    14.     static const int MAXN = 20000 + 10;
    15.     int dp[MAXN] = {};
    17.     void zeroOnePack(int v, int w) {
    18.         for (int j = V; j >= v; j--)
    19.             dp[j] = max(dp[j], dp[j - v] + w);
    20.     }
    22.     void completePack(int v, int w) {
    23.         for (int j = v; j <= V; j++)
    24.             dp[j] = max(dp[j], dp[j - v] + w);
    25.     }
    27.     void multiPack(int v, int w, int s) {
    28.         if (v * s >= V) {
    29.             completePack(v, w);
    30.         } else {
    31.             for (int k = 1; k <= s; k <<= 1) {
    32.                 zeroOnePack(v * k, w * k);
    33.                 s -= k;
    34.             }
    35.             if (s) zeroOnePack(v * s, w * s);
    36.         }
    37.     }
    39. public:
    40.     int N, V;
    42.     void f() {
    43.         cin >> N >> V;
    44.         for (int i = 1; i <= N; i++) {
    45.             int v, w, s;
    46.             cin >> v >> w >> s;
    47.             multiPack(v, w, s);
    48.         }
    49.         cout << dp[V] << endl;
    50.     }
    51. };
    53. // 单调队列优化版本
    54. /* 
    55. 总共 N 个物品，背包体积为 V
    56. 每个物品的体积是 v，价值是 w，数量是 s
    58. 思路：
    59.     原始方程：f[i][j] = max(f[i - 1][j], f[i - 1][j - kv] + kw) (0 <= k <= j/v)
    60.     一维优化后：f[j] = max(g[j - kv] + kw) (0 <= k <= j / v)
    61.     其实可以分组，即对每一个数据为 v, w, s 的物品，进行枚举时，利用 j % v，把 V 分成 v 组
    62.     假设对于首项为0的那组：
    63.         f[0] = f[0]
    64.         f[v] = f[v], f[v - v] + w = f[v], f[0] + w
    65.         f[2v] = f[2v], f[2v - v] + w, f[2v - 2v] + 2w = f[2v], f[v] + w, f[0] + 2w
    66.         ...
    67.         f[kv] = f[kv], f[(k - 1)v] + w, ..., f[0] + kw
    68.     可以转换成
    69.         f[0] - 0w       = f[0]
    70.         f[v] - 1w       = f[v] - w, f[0]
    71.         f[2v] - 2w      = f[2v] - 2w, f[v] - w, f[0]
    72.         ...
    73.         f[kv] - kw      = f[kv] - kw, f[(k-1)v] - (k-1)w, ..., f[0]
    74.     这样就可以用单调队列去维护了，只要在最后的结果那加 kw 就好
    75. */
    76. class Solver2 {
    77.     static const int MAXN = 20000 + 5;
    78.     struct Node {
    79.         int pos, val;
    80.     } q[MAXN];
    81.     int dp[MAXN] = {};
    82.     int N, V;
    83.     void multiPack(int v, int w, int s) {
    84.         for (int i = 0; i < v; i++) {
    85.             int hh = 0, tt = 0, stop = (V - i) / v;
    86.             for (int k = 0; k <= stop; k++) {
    87.                 int val = dp[k * v + i] - k * w;
    88.                 while (hh < tt && q[tt - 1].val <= val) tt--;
    89.                 if (hh < tt && q[hh].pos < k - s ) hh++;
    90.                 q[tt].val = val, q[tt++].pos = k;
    91.                 dp[k * v + i] = q[hh].val + k*w;
    92.             }
    93.         }
    94.     }
    95. public:
    96.     void f() {
    97.         cin >> N >> V;
    98.         int v, w, s;
    99.         for (int i = 0; i < N; i++) {
    100.             cin >> v >> w >> s;
    101.             multiPack(v, w, s);
    102.         }
    103.         cout << dp[V] << endl;
    104.     }
    105. };
    107. int main() {
    108.     Solver2 s;
    109.     s.f();
    110. }