Luogu P4095 [HEOI2013]Eden的新背包问题

题目

求出从前往后的背包\(f_{i,j}\)和从后往前的背包\(F_{i,j}\)。

那么对于询问\((d,e)\)，答案就是\(\max\limits_{i=0}^e f_{d-1,i}+F_{d+1,e-i}\)。

然后就是单调队列优化多重背包。

记物品有\(c[i]\)个，价值为\(v[i]\)，代价为\(w[i]\)。

多重背包的转移\(f[i][j]=\max\limits_{k=0}^{min(c[i],\lfloor\frac j{w[i]}\rfloor)}(f[i-1][j-w[i]*k]+v[i]*k)\)

令\(s=\lfloor\frac j{w[i]}\rfloor,d=j-w[i]*s\)。

则\(f[i][j]=\max\limits_{k=0}^{min(c[i],\lfloor\frac j{w[i]}\rfloor)}(f[i-1][d+(s-k)*w[i]]+v[i]*k)\)

令\(k=s-k\)，则\(f[i][j]=\max\limits_{k=max(0,s-c[i])}^{s}(f[i-1][d+k*w[i]]-v[i]*k)+v[i]*s\)

也就是对于\(f[i][d+k*w[i]\)，我们需要找到前面\(f[i-1][d+K*w[i]]-K*w[i](K\in[k-c[i],k])\)的最大值，然后加上\(k*w[i]\)。

我们将前面的所有\(f[i-1][d+K*w[i]]-K*w[i](K\in[k-c[i],k])\)放进一个单调队列，每次把队首的\(K\)小于\(k-c[i]\)的弹出，然后把当前的\(f[i][d+k*w[i]]\)加入队尾，然后取出队首更新答案。

这里我们可以用一个pair的deque来实现。

#include<bits/stdc++.h>

#define mp make_pair

#define P pair<int,int>

#define fir first

#define sec second

using namespace std;

const int N=1007,V=10007;

int read(){int x;scanf("%d",&x);return x;}

void max(int &a,int b){a=a>b? a:b;}

int c[N],w[N],v[N],d[N],e[N],f[N][V],F[N][V];

void cal(int *f,int i)

{

    for(int d=0,k;d<w[i];++d)

    {

        deque<P>q{mp(0,f[d])};

        for(k=1;k*w[i]+d<=10000;++k)

        {

	    while(!q.empty()&&q.front().fir<k-c[i]) q.pop_front();

            while(!q.empty()&&q.back().sec<=f[k*w[i]+d]-k*v[i]) q.pop_back();

            q.push_back(mp(k,f[k*w[i]+d]-k*v[i])),max(f[k*w[i]+d],q.front().sec+k*v[i]);

        }

    }

}

int main()

{

    int i,d,e,n,q,ans;

    for(n=read(),i=1;i<=n;++i) w[i]=read(),v[i]=read(),c[i]=read();

    for(i=1;i<=n;++i) memcpy(f[i],f[i-1],sizeof f[i]),cal(f[i],i);

    for(i=n;i;--i) memcpy(F[i],F[i+1],sizeof F[i]),cal(F[i],i);

    for(q=read();q;--q)

    {

	d=read()+1,e=read(),ans=0;

	for(i=0;i<=e;++i) max(ans,f[d-1][i]+F[d+1][e-i]);

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

    }

}

或者换成手写队列也行。不过我刚刚写锅了，懒得写了。反正deque常数挺小的。

巴特西

Luogu P4095 [HEOI2013]Eden的新背包问题

最新文章

热门文章