题解 P1776 【宝物筛选_NOI导刊2010提高（02）】

· · 题解

为了学习单调队列优化DP奔向了此题。。。

基础的多重背包就不展开了。设f_{i,j}为选前i个物品，重量不超过j的最大价值，w为重量，v为价值（蒟蒻有强迫症，特别不喜欢把v和w反着搞，weight和value嘛！），直接给转移方程

f_{i,j}=\max\{f_{i-1,j-kw_i}+kv_i\},k\in[0,min\{m,\lfloor \frac j{w_i}\rfloor\}]

显然，f_i都是从f_{i-1}转过来的，所以第一维可以滚掉，得到每次转移的更简化的方程

f_j=\max\{f_{j-kw}+kv\}

这样是O(nmW)的，还是要想办法优化。

众所周知，DP优化的根本原则是去掉无用的状态、利用重复转移的状态。可是这方程一眼根本看不出什么可优化的地方啊。。。。。。

我们要像这位Dalao一样善于发现，他的blog

所以，不管这个想法是怎么来的，我们先把j按模i意义下分组，设j=k_1w+d，那么一组里的d都是同一个值。

然后方程就变成了这样

f_j=\max\{f_{k_1w+d-kw}+kv\} \qquad\qquad\qquad\quad=\max\{f_{(k_1-k)w+d}-(k_1-k)v\}+k_1v

突然看到了k_i-k的重复出现！这也就意味着，在每一组中，有意义的状态只有\lfloor\frac{W-d}w\rfloor种！（W是最大载重）每次总的状态也就只有O(W)了。

设g_k=f_{kw+d}-kv。那么因为有m的限制，所以对于每个k_1，我们需要且只能从max\{g_k|k\in[\max\{0,k_1-m\},k_1]\}转移。对于这样的转移，可以形象地和滑动窗口联系一下，相当于有一个宽度为m的窗口从一边一步步往另一边移动，每移一次都要取出窗口内的最大值。这个就上单调队列维护。

首先枚举d。接着，为了方便滚动，我们从大到小枚举k和k_1，用一个单调队列维护下标在[k_1-m,k_1]范围内的依次递减的若干个g值，因为显然如果有g_x\geq g_y,x<y的话g_y是没有用的。枚举k_1时，每次队首元素超出了范围就把它出队。用现在的队首更新f_j即f_{k_1w+d}。接着下一个元素g_{k_1-m-1}要入队了，把队尾g比这个小的全出队，再让它进来。最后输出f_W即可。

这样就是O(nW)的了，比二进制拆分难理解些但是更优秀了。

结合代码理解会更轻松哦

#include<cstdio>
#define RG register
#define R RG int
#define G c=getchar()
const int N=1e5+9;
int f[N],g[N],q[N];
inline int in(){
    RG char G;
    while(c<'-')G;
    R x=c&15;G;
    while(c>'-')x=x*10+(c&15),G;
    return x;
}
inline int max(R x,R y){return x>y?x:y;}
inline void chkmx(R&x,R y){if(x<y)x=y;}
int main(){
    R n=in(),maxw=in(),maxk,lim,v,w,m,d,i,k,k1,h,t,now;
    for(i=1;i<=n;++i){
        v=in();w=in();m=in();
        for(d=0;d<w;++d){//枚举余数
            maxk=(maxw-d)/w;lim=max(maxk-m,0);//先确定最初的范围
            for(t=0,k=maxk-1;k>=lim;--k){//窗口先扩大宽度到m
                now=f[k*w+d]-k*v;
                while(t&&g[t]<=now)--t;//维护单调性
                g[++t]=now;q[t]=k;
            }
            for(h=1,k1=maxk;~k1;--k1,--k){//可以开始转移了
                if(h<=t&&q[h]>=k1)++h;//接着移动
                if(h<=t)chkmx(f[k1*w+d],g[h]+k1*v);//转移
                if(k<0)continue;//注意窗口可能已经出正数范围了
                now=f[k*w+d]-k*v;
                while(h<=t&&g[t]<=now)--t;//维护单调性
                g[++t]=now;q[t]=k;
            }
        }
    }
    printf("%d\n",f[maxw]);
    return 0;
}