[luogu P1776] 宝物筛选解题报告(单调队列优化DP)

题目链接：

https://www.luogu.org/problemnew/show/P1776

题目：

终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物……这下小FF可发财了，嘎嘎。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了……小FF对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小FF有一个最大载重为W的采集车，洞穴里总共有n种宝物，每种宝物的价值为v[i]，重量为w[i]，每种宝物有c[i]件。小FF希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

题解：

很容易写出状态转移方程$dp_{i,j}=max[dp_{i-1,j-w*k}+v*k],k<=c$

我们要转化为可以单调队列优化的类型

$dp_{i,j}=max[dp_{i-1,d+w*k}-v*k]+v*s,s=\lfloor \frac{j}{w} \rfloor,d=j \mod w$ 枚举k。

众所周知，dp优化的原理就是减少不必要的转移，上述这个状态转移方程就是基于发现最初始的状态转移方程里的j只能从j在模w意义下的同余系转移而得到。因而我们枚举余数d

那么如何用单调队列维护就很显然了，对于每一个余数d维护一个单调队列即可

代码

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

const int N=4e4+;

int n,W,ans,tmp;

int dp[N],q1[N],q2[N];

inline int read()

{

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int main()

{

    n=read();W=read();

    for (int i=;i<=n;i++)

    {

        int v=read(),w=read(),c=read();

        if (w==)

        {

            ans+=v*c;

            continue;

        }

        c=min(c,W/w);

        for (int d=;d<w;d++)//枚举余数

        {

            int K=(W-d)/w;//最大的整除数

            int head=,tail=;

            for (int k=;k<=K;k++)//枚举整除数

            {

                int now=dp[d+w*k]-v*k;

                while (head<=tail&&now>=q1[tail]) --tail;

                ++tail;

                q1[tail]=now;

                q2[tail]=k;

                while (head<=tail&&c<k-q2[head]) head++;

                dp[d+w*k]=max(dp[d+w*k],q1[head]+v*k);

                tmp=max(dp[d+w*k],tmp);

            }

        }

    }

    printf("%d\n",tmp+ans);

    return ;

}

巴特西

[luogu P1776] 宝物筛选解题报告(单调队列优化DP)

题目链接：

题目：

代码

最新文章

热门文章

巴特西

[luogu P1776] 宝物筛选 解题报告(单调队列优化DP)

题目链接：

题目：

代码

最新文章

热门文章

[luogu P1776] 宝物筛选解题报告(单调队列优化DP)