题目描述

blablabla

算法1

C++ 代码

#include <cstdio>
#include <iostream>
struct node {
    int val, pos;
}q[20010];
int dp[20010];

int main() {
    int n, m;
    std::cin >>n>>m; 
    for (int i = 0; i < n; i++) {
        int v, w, s;
        std::cin >> v >> w >>s;
        for (int j = 0; j < v; j++) {//v的余数j
            int t = 0, h = 0;
            for (int k = 0; k <= (m-j)/v; k++) {//使用k个物品i
                int val = dp[j+k*v] - k*w;//这次迭代目标是更新dp[j+kv]的值
                //val是放入滑动窗口的值。dp[j+k*v] - k*w;方便维护，和后面的dp[j+k*v] = q[h].val+k*w相呼应。由第k项到k+1项就会多一个w，以此类推
                //在k轮的时候执行代码所描述的操作
                //在k+1轮的时候
                //如果滑动窗口的最大值是在k轮的时候放入单调队列q里面的，即q[h].val = dp[j+k*v]-k*w，到第k+1轮更新dp数组的时候是dp[j+(k+1)*v] = q[h].val+(k+1)*w = dp[j+k*v]-k*w+(k+1)*w = dp[j+k*v]+w
                //如果滑动窗口的最大值是k+1轮生成的，即q[h].val = dp[j+(k+1)*v]-(k+1)*w，到k+1轮更新dp数组的时候是dp[j+(k+1)*v] = q[h].val+(k+1)*w = dp[j+(k+1)*v]-(k+1)*w+(k+1)*w = dp[j+(k+1)*v]
                //即第k+1项可以从dp[j+(k+1)*v]，dp[j+k*v]+w中选一个最大的，这里只是两项，多几项的时候是一个滑动窗口
                if (k - q[h].pos > s) h++;
                while (h < t && val >= q[t-1].val) t--;
                q[t].val = val; q[t++].pos = k;
                dp[j+k*v] = q[h].val+k*w;//滑动窗口，最大的值，经过以上一顿操作之后更新dp[j+k*v]
            }
        }
    }
    std::cout << dp[m];
    return 0;
}