$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

我们知道，任何一个数都可以表示成若干个 $2^k$ 之和。
只要能用这种方法表示出 $1 - s$ 中的所有数，就可以优化成 $\log$ 的复杂度。
那如何用若干个 $2^k$ 表示 $1 - s$ 的所有数呢？

如 $s = 200$，可以拆成 $1,2,4,8,16,32,64,73$。即若干个 $2^k$ 加上剩余的数。

顺带一提，可以用单调队列继续优化，但一直没学。
大致是利用余数的一个性质，每次只更新一个值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 4e4 + 15;
int n, m;
long long f[M];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int v, w, s; scanf("%d%d%d", &w, &v, &s);
        for (int k = 1; k <= s; k <<= 1) {
            for (int j = m; j >= k * w; j--) f[j] = max(f[j], f[j - k * w] + k * 1ll * v);
            s -= k;
        }
        if (s)
            for (int j = m; j >= s * w; j--) f[j] = max(f[j], f[j - s * w] + s * 1ll * v);
    }
    printf("%d\n", f[m]);
    return 0;
}