单调队列优化多重背包

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1001;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, C, q[10001];
LL f[10001], val[10001];
main() {
    N = read(); M = read(); C = read();
    for(int i = 1; i<= N; i++) {
        int w = read(), v = read(), d = read();
        for(int b = 0; b < w; b++) {//b = j % w  原体积为j = k * w + b
            for(int k = 0, h = 1, t = 0, j = b; j <= C; k++, j += w) {
                int a = k * v, tmp = f[j] - a;// a = j / w * v = k * v
                while(h <= t && tmp > val[q[t]]) t--;
                q[++t] = k; val[q[t]] = tmp;//由于这里的val需要被更新过后才能使用，因此不用清空
                while(h <= t && q[h] + d < k) h++;//需要的物品超过d个
                f[j] = val[q[h]] + a;
            }
        }
    }
    for(int i = 1; i <= M; i++) {
        int a = read(), b = read(), c = read();//
        for(int j = C; j >= 0; j--)//枚举一下体积
            for(int k = 0; k <= j; k++)
                f[j] = max(f[j], f[j - k] + (a * k + b) * k + c);
    }
    cout << f[C];
    return 0;
}