二刷提高课，题解目录在这里— 提高课的题解目录

第一次怎么看都看不懂，第二次看起来就容易理解多了
首先分析我们需要做什么，我们枚举每一次j最多都会向前枚举s次（不越界）
这就导致了我们的状态转移并不是o(1)的，而是o(n)的
然后看我们浪费的操作在哪里，可以发现我们每次都会向前找s位选取最大的（相对）
我们抽象一下：也就是遍历j的过程中每次都向前枚举s位来寻找最大值
这不就是我们做过的滑动窗口吗，那么我们就可以用单调队列来实现转移的操作
使得我们每次用o(1)的复杂度来找到最大值
还有一个注意的点就是我们每此比较的点的绝对数量都不同从y总的图来看每次都会多-w
但是我们在同一条j中（也就是同一行）相对大小是不变的都是对前一项多w
这就是我们增加偏移量的原因，注意这并不影响运算（我们存的还是真实值）
这里解释一下：即使一个数比另一个数大，但是在公式中可能加过w之和更小了，
所以其实存的还是另一个数（真实值），但是当我们计算转移时，又把应该加的w加进去了，所以是真实的最大值
也就是我们获得了相对大小，然后再状态转移中是可以正确转移的
还有一个细节就是我们如果使用二维数组会导致开了1e8的内存会爆内存
所以这里用一维优化，但是我们发现，当我们用到的上一层必须是比较出来的（并不是直接使用）不能简单地从后向前
所以必须使用滚动数组来保存上一层的结果
滚动数组：可以理解为用一维数组多次表示不同层的内容

#include<iostream>
#include<cstring>
using namespace std;
const int N=20010;
int f[N],g[N],q[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof f);
        for(int j=0;j<v;j++)//可以理解将j分为多组
        {
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v)
            {
                while(hh<=tt&&k>q[hh]+s*v)hh++;//每个j只能向前枚举s位（因为只有s个物品）
                while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w)tt--;
                q[++tt]=k;
                f[k]=g[q[hh]]+(k-q[hh])/v*w;
            }
        }
    }
    cout<<f[m];
    return 0;
}