$\LARGE\color{orange}{刷题日记(算法提高课)}$

$O(n^2)$ 优化做法的考虑方式跟 AcWing 3. 完全背包问题 很像

不难写出，朴素的状态转移方程为 $f[i][j]=max(f[i-1][j],\ f[i-1][j-v]+w,\ f[i-1][j-2v]+2w,\ \dots,\ f[i-1][j-sv]+sw)$

考虑与完全背包相同的思路，将上述表达式往后写一位，有 $f[i][j-v]=max(f[i-1][j-v],\ f[i-1][j-2v]+w,\ f[i-1][j-3v]+2w,\ \dots,\ f[i-1][j-sv]+(s-1)w,\ f[i-1][j-(s+1)v]+sw)$

需要说明的是，在完全背包里面 $s$ 是在背包体积为 $j$ 时第 $i$ 个物品最大能选的个数，因此在背包体积变为 $j-v$ 时，最大个数也相应变为 $s-1$

在多重背包这里的 $s$ 表示第 $i$ 个物品最大可选的个数，并没有体积的限制

注意到，$f[i][j]$ 的状态只会由 $f[i-1][j],\ f[i-1][j-v],\ f[i-1][j-2v],\ \dots,\ f[i-1][j-sv]$ 这些转移过来

这里一共有 $s+1$ 个状态，并且当 $j$ 取定时，不断重复 $j-v,\ j-2v,\ ,\ j-3v,\ \dots$ 这个过程，最终我们一定可以得到一个余数

如果我们将余数相同的状态看成一个组的话，$f[i][j]$ 的值只会由同组当中的状态转移而来

因此对于所有的状态，我们只需要枚举余数 $r$，在此余数 $r$ 的基础上，不断加 $v$ 来表示同组的状态

如此这般，我们一定可以枚举出所有的状态，并且也可以求出所有状态的值

由于我们每一次都是求同组状态中，状态数为 $s+1$ 的窗口的最大值，因此这里可以用单调队列来处理

关于单调队列最基本的应用，可以去看 AcWing 154. 滑动窗口

在这里我们重点说明一下最重要的那四个步骤要如何做：

我们定义 $q[i]$ 为单调队列数组，存储的是状态的下标；$f[i]$ 为当前状态数组，存储的是该状态的值； $g[i]$ 为上次循环的 $f[i]$ 数组的备份

• 判断队头元素何时出队：

我们当前枚举的状态记为 $k$ ，记同组余数为 $r$ ，那么 $k$ 可以表示为 $k=r+t*v$ ，$t$ 为相当于第一个状态的偏移量

由于窗口元素为 $s+1$ 个，那么当「当前状态」与「队头状态」之间相差 $s$ 个状态时，我们便让「队头状态」出队（这里需要包括当前状态，因此中级差 $s$ 个）

即 $q[hh]<k-s*v$

• 判断何时调整队列使其保证单调性

只要队尾元素的状态值小于等于当前状态是数值，那么便让其弹出

由于各个状态的数值都加上了一个偏移量，因此在比较时我们需要减去该偏移量

即 $g[q[tt]]-(q[tt]-r)/v*w\le g[k]-(k-r)/v*w$

• 向队列插入元素

直接将状态的表示插入即可，即 $q[++tt]=k$

• 对 $f[i]$ 数值进行赋值

队头元素表示当前窗口的最大值，也就是我们当前的状态需要从队头元素状态转移过来

同样需要加上一个偏移量（相对于队头元素的），即 $f[k]=g[q[hh]]+(k-q[hh])/v*w$

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e4 + 10;

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 r = 0; r < v; r++)
        {
            int tt = -1, hh = 0;
            for(int k = r; k <= m; k += v)
            {
                if(hh <= tt && q[hh] < k - s * v) hh++;
                while(hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[k] - (k - r) / v * w) tt--;
                q[++tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}