python/TangDou/AcWing/BeiBao/6_ErWei.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;  // 物品种类上限
const int M = 20010; // 背包容量上限
int n, m;

int f[N][M]; // 前i个物品，在容量为j的限定下，最大的价值总和
int q[M];    // 单调优化的队列,M是背包容量上限，说明q[]里面保存的是体积

// 二维+队列[k-s*v,k],队列长s+1
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) { // 考虑前i种物品
        int v, w, s;               // 体积、价值、个数
        cin >> v >> w >> s;
        // 下面的j,k是一起用来描述剩余体积的,之所以划分成两层循环，是因为依赖的前序是按v为间隔的依赖，并且，是有个数限制的依赖
        // j:按对体积取模分组：0表示剩余空间除以当前物品的体积余数是0
        // k:分组内的每一个体积,注意：这里的体积不一定都是合法的，因为数量是有限制的
        // 单调队列的意义：查找前面k-s*v范围内的价值的最大值，是一个单调递减的队列，队头保存的是获取到最大值的最近体积
        for (int j = 0; j < v; j++) {         // 按余数分组讨论
            int hh = 0, tt = -1;              // 全新的单调下降队列
            for (int k = j; k <= m; k += v) { // 与j一起构成了有效体积
                // 1、讨论到第i个物品时，由于它最多只有s个，所以有效的转移体积最小是k-s*v,更小的体积将被去除
                if (hh <= tt && q[hh] < k - s * v) hh++;
                // 2、处理队尾,下一个需要进入队列的是f[i-1][k]，它是后来的，生命周期长，可以干死前面能力不如它的所有老头子,以保证一个单调递减的队列
                while (hh <= tt && f[i - 1][q[tt]] + (k - q[tt]) / v * w <= f[i - 1][k]) tt--;
                // 3、k入队列
                q[++tt] = k;
                // 4、队列维护完毕，f[i-1][k]已经进入队列,f[i][k]可以直接从队头取出区间最大值更新自己
                f[i][k] = f[i - 1][q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}