《算法竞赛进阶指南》0x59单调队列优化DP 单调队列优化多重背包

题目链接：https://www.acwing.com/problem/content/description/6/

通过单调队列优化多重背包，从第i-1阶段向第i阶段过渡，将所有可能的决策包含在单调队列中，队列中维护的是一个递减的决策集合，对应的函数值也是递减的，及时去除不可能是最优的解。

在O(N*M)时间内可以得出结果。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1010,M=20010;
ll W[N],V[N],C[N];
ll f[M];
int q[N];
int n,m;
int calc(int i,int u,int k){
    return f[u+k*V[i]]-k*W[i];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&V[i],&W[i],&C[i]);
        for(int u=0;u<V[i];u++){//每一层利用上一层的数据建立队列，故每次都是全新的单调队列 
            ll maxp=(m-u)/V[i];
            int l=1,r=0;
            //从大到小插入，保证索引下降的情况下函数值一定下降 
            for(int k=maxp-1;k>=max(maxp-C[i],0ll);k--){
                while(l<=r && calc(i,u,q[r])<=calc(i,u,k))r--;//维护队尾的单调性 
                q[++r]=k; 
            }
            for(int p=maxp;p>=0;p--){
                if(l<=r && q[l]>p-1)l++;
                if(l<=r)
                    f[u+p*V[i]]=max(f[u+p*V[i]],(ll)calc(i,u,q[l])+p*W[i]);
                if(p-C[i]-1>=0){//保证决策可行性 
                    while(l<=r && calc(i,u,q[r])<=calc(i,u,p-C[i]-1))r--;
                    q[++r]=p-C[i]-1;
                }
            }
        }
    }
    
    ll ans=0;
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);
    cout<<ans<<endl;
    
    return 0;
}