洛谷1776 宝物筛选

题意

多重背包问题。

题解

单调队列优化多重背包。

$$f[i][j] = \max_{k=0}^{num[i]} f[i-1][j-k\times c[i]]+k\times w[i]$$

令 $a = j \mod c[i] \ , \ b = \lfloor \dfrac{j}{c[i]} \rfloor $ ：

$$f[i][j] = \max_{k=b-num[i]}^{b} \{f[i-1][a+k\times c[i]]-k\times w[i]\} + b\times w[i]$$

当 $a$ 确定时，可以发现就是维护一个长度为 $num[i]$ 的队列的最大值。所以枚举所有的 $a$ ，用单调队列维护即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,w,a,b,c,ans,q[40005],f[40005],p[40005];

signed main()
{
    n=read(); w=read();
    for (int i=1;i<=n;i++)
    {
        a=read(); b=read(); c=read(); c=min(c,w/b);
        for (int j=0;j<b;j++)
        {
            int ft=1,bk=0,maxk=(w-j)/b;
            for (int k=0;k<=maxk;k++)
            {
                int cur=f[k*b+j]-k*a;
                while (ft<=bk && p[ft]<k-c) ft++;
                while (ft<=bk && q[bk]<=cur) bk--;
                q[++bk]=cur; p[bk]=k;
                f[k*b+j]=max(f[k*b+j],q[ft]+k*a);
                ans=max(ans,f[k*b+j]);
            }
        }
    }
    printf("%d",ans);
    return 0;
}