洛谷P1776 宝物筛选

一道很好的单调队列优化多重背包入门题
令\(v[i]\)表示重量，\(w[i]\)表示价格 ，\(c[i]\)表示最多可放的数量，不难推出朴素的转移方程如下：

#include <bits/stdc++.h>

using namespace std;

int n, m, zero, v[(int)1e5], w[(int)1e5], c[(int)1e5], f[105][(int)2e5];

struct S { //习惯开结构体QwQ
    int id, w;
}q[(int)2e5];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i] >> c[i];
    for(int i = 1; i <= n; ++i) {
        if(!v[i]) { //处理重量为0的物品
            zero += w[i]*c[i];
            continue;
        }
        for(int r = 0, h = 0, t = 0; r < v[i]; ++r, h = t = 0) //h，t记得清零
            for(int j = r, s = 0; j <= m; j += v[i], ++s) {
                while(h < t && q[t-1].w < f[i-1][j]-s*w[i]) --t; //--维护
                q[t++] = S{s, f[i-1][j]-s*w[i]};                 //--队列
                while(h < t && q[h].id < s-c[i]) ++h;            //--单调性
                f[i][j] = q[h].w+s*w[i];
            }
    }
    cout << zero+f[n][m];
    return 0;
}

洛谷P1776 宝物筛选

原文：https://www.cnblogs.com/dummyummy/p/9644515.html