单调队列优化DP ——P1776 宝物筛选_NOI导刊2010提高（02）

joe19025 · 2018-08-10 03:16:36 · 题解

题目链接

解法

直观做法

是不是很眼熟？

没错，就是开始学DP时，天天出现的背包问题（这里不做过多解释，不会的话点背包问题，查看相关论文）。

状态转移方程（很显然）：

那么这个的时间复杂度一看就很暴力，肯定是AC不了的。 那么该怎么办呢？

正解

闲着没事干瞎推

设j=k_1*w[i]+d

合并同类项

由于k_1只和j有关，可以提出：

这都什么乱七八糟的，有卵用？！接着往下看

我们设g[i][k]=f[i-1][k*w[i]+d]-k*v[i]

所以问题就可以就变成下面的了：

这可以上单调队列了！

所以每层只需要逐个枚举d，然后再枚举k，一个单调队列优化一下，就好啦！分层分块思想。

最后加一个滚动数组优化，要不会爆内存。

这就AC啦！妙哉~

分析

这个题利用的是单调队列的性质，但是单调队列不能处理形如:max(f[i-k*x]+k*y)的问题，因为其中又加了一个变量k*y, i-k*x会随i改变对应位置,这样对于每个f[j]在计算不同的f[i]时会要有不同的增量。

我们对于这个问题的解决方法是将状态转移方程进行一定的转化，转化成单调队列能解决的形式，用单调队列进行加速。

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define eps 1e-12
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;

int main()
{
    long long f[40004][2];
    long long now=1;
    long long pre=0;
    long long w[105];
    long long v[105];
    long long m[105];
    long long n,W;
    scanf("%lld%lld",&n,&W);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&v[i],&w[i],&m[i]);
    memset(f,0,sizeof(f));
    long long q[40005][2];
    for(int i=1;i<=n;i++)
    {
        for(int d=0;d<w[i];d++)
        {
            int head=0,tail=0;
            for(int k=0;k*w[i]+d<=W;k++)
            {
                while(head<tail&&q[head][0]<k-m[i])head++;
                while(head<tail&&q[tail-1][1]<f[k*w[i]+d][pre]-k*v[i])tail--;
                q[tail][0]=k;
                q[tail][1]=f[k*w[i]+d][pre]-k*v[i];
                tail++;
                f[k*w[i]+d][now]=q[head][1]+k*v[i];
            }
        }
        swap(now,pre);
    }
    printf("%lld",f[W][pre]);
    return 0;
}