HEOI2013 Eden的新背包问题

wjh15101051's space

卧薪尝胆，厚积薄发。

HEOI2013 Eden的新背包问题

Date: Sat Aug 18 19:20:59 CST 2018

In Category: NoCategory

Description：

多重背包，支持询问去掉某件物品后容量为 $k$ 时的最大值。

$1\le n \le 1000$ $1\le k\le 1000$ $1\le q\le 3\times 10^5$

Solution：

多重背包可以单调队列优化成 $O(nk)$ ，预处理一个前缀背包 $f[i][j]$ 表示前 $i$ 个物品容量为 $j$ ，同理预处理一个后缀背包，询问时枚举前面选多少合并即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std; 

int n;

#define MAXN 1010

int u[MAXN],v[MAXN],w[MAXN];

int f[MAXN][MAXN];

int g[MAXN][MAXN];

int q[MAXN],head,tail;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d%d",&u[i],&v[i],&w[i]);

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

	{

		for(int j = 0;j < u[i];++j)

		{

			head = 1;tail = 0;

			q[++tail] = j;

			for(int k = j + u[i];k < MAXN;k += u[i])

			{

				while(head < tail && (k - q[head]) / u[i] > w[i])++head;

				f[i][k] = max(f[i][k],f[i - 1][q[head]] + (k - q[head]) / u[i] * v[i]);

				while(head <= tail && f[i - 1][k] >= f[i - 1][q[tail]] + (k - q[tail]) / u[i] * v[i])--tail;

				q[++tail] = k;;

			}

		}

		for(int k = 0;k < MAXN;++k)f[i][k] = max(f[i][k],f[i - 1][k]);

	}

	for(int i = n;i >= 1;--i)

	{

		for(int j = 0;j < u[i];++j)

		{

			head = 1;tail = 0;

			q[++tail] = j;

			for(int k = j + u[i];k < MAXN;k += u[i])

			{

				while(head < tail && (k - q[head]) / u[i] > w[i])++head;

				g[i][k] = max(g[i][k],g[i + 1][q[head]] + (k - q[head]) / u[i] * v[i]);

				while(head <= tail && g[i + 1][k] >= g[i + 1][q[tail]] + (k - q[tail]) / u[i] * v[i])--tail;

				q[++tail] = k;

			}

		}

		for(int k = 0;k < MAXN;++k)g[i][k] = max(g[i][k],g[i + 1][k]);

	}

	int l;

	scanf("%d",&l);

	int p,s;

	for(int i = 1;i <= l;++i)

	{

		scanf("%d%d",&p,&s);++p;

		int ans = 0;

		for(int k = 0;k <= s;++k)

		{

			ans = max(ans,f[p - 1][k] + g[p + 1][s - k]);

		}

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

	}

	return 0;

}

In tag: DP-单调队列优化DP

wjh15101051