思路

1. $f[i][j] = max{f[i-1][j], f[i-1][j-v] + w, f[i-1][j- 2\*v] + 2\*w, … , f[i-1][j - k\*v]}$
2. $f[i][j+v] = max{f[i-1][j+v], f[i-1][j] + w, f[i-1][j-v] + 2 \* w, …, f[i-1][j - (k+1)\*v]}$
3. 从上面两个公式可以发现，$f[i][j]$ 取决于 $f[i-1][j-v]$, $f[i-1][j-2\*v]$ 等项，这些项是关于 $v$ 的等差数列，而且 $(j - k\*v)%v$ 的余数相同；
4. 所以我们可以对于 $v$ 根据余数切分成 $[0, v-1]$，这样做的好处有：余数相同的一组，最大值可以用优先队列求解（对比$f[i][j]$ 和 $f[i][j+v]$）
5. 对于一个大小为 $m/v$ 的数组，使用优先队列求解的时间复杂度是 $O(m/v)$; 整体的时间复杂度可以优化到 $O(nm)$;

时间复杂度 $O(nm)$

代码（参考y总）

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

const int N = 1010, M = 20010;

int f[N][M] = {0}, q[M];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1, v, w, s; i <= n+1; ++i) {
        cin >> v >> w >> s;

        for (int j = 0; j < v; ++j) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                // 不选第 i 个物品
                f[i][k] = f[i-1][k];

                if (hh <= tt && k - q[hh] > s*v) hh++;

                if (hh <= tt) {
                    f[i][k] = max(f[i-1][k], f[i-1][q[hh]] + (k - q[hh]) / v * w);
                }

                // 滑动窗口内的值不是 f[i], 而是 f[i] + w的权重;
                // f[i][j] = max{f[i-1][j], f[i-1][j-v] + w, f[i-1][j- 2*v] + 2*w, ... , f[i-1][j - k*v] + k*w}
                // 比如这里的第 k 个和第 2 个， 差为(k - 2)*w
                while (hh <= tt && f[i-1][q[tt]] + (k - q[tt]) / v * w <= f[i-1][k]) tt--;
                q[++tt] = k;
            }
        }
    }
    cout << f[n][m] << endl;
}

空间优化

1. $g[[j]$ 保存 $f[i-1][j]$; $f[j]$ 保存 $f[i][j]$
2. 使用倒序优化掉 $g[j]$ 可行否 ？不行，因为 $f[i][j]$ 是由前面的项计算出来的， 所以另开一个 $g$ 数组存 $f[i-1][j]$

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;

const int M = 20010;
int f[M], q[M], g[M];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0, v, w, s;i < n;++i) {
        cin >> v >> w >> s;

        // g[j] 存储 f[i-1][j]
        // f[j] 存储 f[i][j]
        memcpy(g, f, sizeof(f));
        for (int j = 0;j < v; ++j) {
            int hh = 0, tt = -1;
            for (int k = j;k <= m;k += v) {
                if (hh <= tt && k - q[hh] > s*v) hh++;

                if (hh <= tt) {
                    f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                }

                while (hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) tt--;
                q[++tt] = k;
            }
        }
    }
    cout << f[m] << endl;
}