分析:

公式推理：

公式转换

引用这位同学的题解： https://www.acwing.com/solution/content/6500/

1.因此，可以转换成一下的形式：

f[i][j]    =     f[i - 1][j]
f[i][j+v]  = max(f[i - 1][j] +  w,  f[i - 1][j+v])
f[i][j+2v] = max(f[i - 1][j] + 2w,  f[i - 1][j+v] +  w, f[i - 1][j+2v])
f[i][j+3v] = max(f[i - 1][j] + 3w,  f[i - 1][j+v] + 2w, f[i - 1][j+2v] + w, f[i - 1][j+3v])

统一：
f[i][j]    =     f[i - 1][j]
f[i][j+v]  = max(f[i - 1][j], f[i - 1][j+v] - w) + w
f[i][j+2v] = max(f[i - 1][j], f[i - 1][j+v] - w, f[i - 1][j+2v] - 2w) + 2w
f[i][j+3v] = max(f[i - 1][j], f[i - 1][j+v] - w, f[i - 1][j+2v] - 2w, f[i - 1][j+3v] - 3w) + 3w
...

2.由于计算顺序是从f[I, j -z得i- 1层的数组。g数组是滚动数组，存放上一层
这样，每次入队的值是 g[q[k]] - (q[k] - j) / v * w
举例说明：





f[i][j+3v] = max(f[i - 1][j], f[i - 1][j+v] - w, f[i - 1][j+2v] - 2w, f[i - 1][j+3v] - 3w) + 3w 这个公式

g[q[k]]就是 f[i - 1][j + 2v]
q[k] - j / v * w 就是 2


最后的答案是 g[q[tt]] - (q[tt] - j) / v * w + (k - q[hh]) / v * w
(k - q[hh]) / v * w的原因是：

g[q[hh]] 是f[i - 1][j + 2v]
根据最后的公式：答案应该是 f[i][j + 3v] = max(f[i - 1][j + 2v] - 2w) + 3w
对应着：**g[q[hh]] - (q[hh] - j) / v * w + (k - j) / v * w**

模拟：

代码：

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

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


int main()
{
    int n, m;cin >> n >> m;
    while(n--)
    {
        int v, w, s; cin >> v >> w >> s;
        /*由于计算顺序是从f[I, j - sv], f[I, j - (s - 1)v]……f[I, j]，
        因此计算f[I, j]的时候，公式中i- 1层都已经被更新过，因此要用滚动数组存放没有被计算过得i- 1层的数组。*/
        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)
            {
                /*利用滑动窗口把长度为s窗口中每种情况赋值*/
                while(hh <= tt && k - s * v > q[hh])hh++;
                while(hh <= tt && g[k] - (k - j) / v * w >= g[q[tt]] - (q[tt] - j) / v * w)tt--;
                q[++tt] = k;
                /*通过f的公式，f[i, j] = max(f[I - 1, j - sv] + sw, f[I - 1, j - (s - 1)v] + (s - 1) w ……, f[I - 1, j])
                g[q[hh]]代表上一次层的最大值f[i - i]
                */
                f[k] = g[q[hh]] + (q[tt] - q[hh]) / v * w;
            }
        }
    }
    cout << f[m] <<endl;
    return 0;
}