多重背包问题Ⅲ单调队列优化

#include <iostream>
#include <cstring>

using namespace std;

const int NUMBER = 1010, VOL = 20010;

int number, max_vol;
int vols[NUMBER], vals[NUMBER], cnt[NUMBER];
int dp[VOL], _dp[VOL];
int queue[VOL];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> number >> max_vol;
    for (int i = 1; i <= number; ++i) cin >> vols[i] >> vals[i] >> cnt[i];

    for (int i = 1; i <= number; ++i) {
        memcpy(_dp, dp, sizeof dp);

        for (int r = 0; r < vols[i]; ++r) {
            int head = 0, tail = -1;

            for (int j = r; j <= max_vol; j += vols[i]) {
                while (head <= tail && j - queue[head] > vols[i] * cnt[i]) head++;
                while (head <= tail && _dp[j] >= _dp[queue[tail]] + (j - queue[tail]) / vols[i] * vals[i]) tail--;
                queue[++tail] = j;
                dp[j] = _dp[queue[head]] + (j - queue[head]) / vols[i] * vals[i];
            }
        }
    }

    cout << dp[max_vol] << endl;

    return 0;
}