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

Owen_codeisking · 2018-07-13 19:49:12 · 题解

引言

本蒟蒻在wzms的机房中听教练讲用单调队列优化dp没听懂，所以特地来刷一刷裸的多重背包。

多重背包与01背包和完全背包不一样的地方在于，它处于一个两者之间的境地，所以多重背包注定需要一些神奇的数据结构优化。

若你单调队列没学过，请你看一看 P1886 滑动窗口

正文

首先声明，我的变量名与题中不一样。我定义N为物品个数，M为背包总量，V_{i}是第i件物品的重量，W_{i}是第i件物品的价值，C_{i}是第i件物品的可放总量，F_{i}表示在i重量下能收获的最大价值。

可知当k\in[0,C_{i}],u\in[0,v[i])时，有

那么在已知F[u]是由F[u+t*v[i]]-t*w[i]这个状态转移过来时

那么定义能放下的最大当前物品个数为maxp，易得

而t\in[max(maxp-j-c[i],0),maxp-j],j\in[0,maxp]时

这一状态会被重复计算，这个时候单调队列就能排上用场了。

再定义calc(i,u,k)=F[u+k*v[i]]-k*w[i]，单调队列首尾为l,r,那么可知状态转移方程

有且仅当在l<=r时发生转移。

那么我们理一下思路

（0）预处理时F[0]=0,F[i]=-INF(i\in[1,m])

（1）每次读进来一组V_{i} ,W_{i} ,C_{i} 时,将m重量进行模V_{i}分组，先将物品个数maxp到max(maxp-c[i],0)之间进入单调队列，其维护放入物品个数k单调递减，所对应的calc也单调递减。只要当l<=r且calc(i,u,q[r])<=calc(i,u,k)时,r--。否则将k压入队列

（2）逐一枚举k从maxp到0，只要当l<=r且q[l]>k-1时,l++。但若k-C_{i}-1>=0，则将新的物品个数在满足（1）条件下压入队列以保证下一轮的状态转移

（3）在F_{i}(i\in[1,m])中取出最大值ans，输出ans

#include <bits/stdc++.h>
#define maxn 110
#define maxm 100010
using namespace std;
int n,m;
int v[maxn],w[maxn],c[maxn];
int f[maxm],q[maxm];

int calc(int i,int u,int k){
    return f[u+k*v[i]]-k*w[i];
}

int main()
{
    memset(f,0xcf,sizeof(f));
    scanf("%d%d",&n,&m);
    f[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&w[i],&v[i],&c[i]);
        for(int u=0;u<v[i];u++){
            int l=1,r=0;
            int maxp=(m-u)/v[i];
            for(int k=maxp-1;k>=max(maxp-c[i],0);k--){
                while(l<=r&&calc(i,u,q[r])<=calc(i,u,k)) r--;
                q[++r]=k;
            }
            for(int k=maxp;k>=0;k--){
                while(l<=r&&q[l]>k-1) l++;
                if(l<=r) f[u+k*v[i]]=max(f[u+k*v[i]],calc(i,u,q[l])+k*w[i]);
                if(k-c[i]-1>=0){
                    while(l<=r&&calc(i,u,q[r])<=calc(i,u,k-c[i]-1)) r--;
                    q[++r]=k-c[i]-1;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        ans=max(f[i],ans);
    printf("%d\n",ans);
    return 0;
}

补充：正常476ms，开了O_{2}\quad 84ms，可能还有些神奇的优化能让正常的时间快一些，留给读者自己思考。