P1776 宝物筛选

renfei147 · 2019-11-02 21:17:50 · 个人记录

居然一直以为多重背包只能二进制拆分做。。这里记录一下单调队列做法。

设v为价值，w为重量，c为数量，则原始转移方程为

然后我们把背包容量按照模w的余数分类。设a=\left\lfloor\frac{j}{w_i}\right\rfloor，b=j\bmod w_i

把\max中含a的提出来

这样\max里就和a无关了，并且k的区间两端点随a单调递增，于是可以使用单调队列优化。

当然上面的式子里k的范围写完整是\max\{a-c_i,0\}\leq k\leq a

由于我们把会用到的值存在了单调队列里，所以可以直接一维数组正序递推，不用担心覆盖问题。

这样每一类的背包容量都是线性递推，时间复杂度O(NW)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[100000];
int q[100000],idx[100000],head,tail;
int main()
{
    int n,W;
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)
    {
        int v,w,c;
        scanf("%d%d%d",&v,&w,&c);
        for(int b=0;b<w;b++)
        {
            head=tail=0;
            for(int a=0;a<=(W-b)/w;a++)
            {
                int tt=dp[b+a*w]-a*v;
                while(head<tail&&q[tail-1]<=tt)tail--;
                idx[tail]=a;
                q[tail++]=tt;
                while(head<tail&&idx[head]<a-c)head++;
                dp[b+a*w]=q[head]+a*v;
            }
        }
    }
    printf("%d\n",dp[W]);
    return 0;
}