题目描述

注释版，仅记录。

算法1

(暴力枚举) $O(nm)$

C++ 代码

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=20010;

int n,m;
int f[N],g[N],q[N];     //g[N]存的是上一层的f值，避免被更新掉。

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;

        memcpy(g,f,sizeof f);

        for(int j=0;j<v;j++)
        {
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v)  //k是当前余数情况下的不同的体积
            {
                while( hh <= tt && q[hh]<k-s*v) hh++;   //如果队头元素不满足题意，需要把队头元素提前
                if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);   //每次都选取同一余数的的最大值，即队头元素对应的f值，加上转移的总收益，即(k-q[tt])/v*w；
                while(hh<=tt &&  g[q[tt]]+(k-q[tt])/v*w <= g[k]) tt--;  //如果最大值和转移收益的总和还不如要加入的价值大，那么删去队尾元素，保证单调性。
                q[++tt]=k;
            }
        }


    }
    cout<<f[m]<<endl;

    return 0;
}