洛谷 P4095 [HEOI2013]Eden 的新背包问题

洛谷 P4095 [HEOI2013]Eden 的新背包问题

原题链接

Solution

算法：多重背包

我们平时写的多重背包中，(f[i][j]) 表示到第 (i) 个物品，占用体积为 (j) 时，获得的最大价值。

但是这道题中要求删去物品，如果每次询问都跑一遍多重背包显然会 (TLE)，我们考虑优化。

可以设 (f[i][j]) 表示到第 (i) 个物品，但是删去它，占用体积为 (j) 时，获得的最大价值，诶，这样不就是 (f[i - 1][j]) 嘛=-=。

但是这样会有问题，我们没有计算 (i) 之后物品的贡献，所以也不行。

换一个角度思考，题目不是要求删一个物品吗？那我们正着跑一边多重背包，再倒着跑一遍，如果删去 (x) 那么输出 (max(f1[x - 1][j] + f2[x + 1][V - j])) 即可。

另外，朴素的多重背包还是无法通过此题的，要进行优化，这里我用的是二进制拆分优化多重背包。

如果不会的话，详见我的博客 洛谷 P1833 樱花

Code

#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

const int N = 1010;
const int Q = 3e5 + 10;
const int M = 1000;
int a[N], b[N], c[N];
int n, m, num;
ll w[N * 15], v[N * 15];
int id[N * 15];
ll f1[N * 15][N], f2[N * 15][N];		//f1：正着	f2：反着	注意：第一维不能压掉，我们还要记录第几个物品

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

void prework(){						//二进制拆分模板
	for(int i = 1; i <= n; i++){
		int tmp = 1;
		while(c[i]){
			w[++num] = tmp * a[i];
			v[num] = tmp * b[i];
			id[num] = i;
			c[i] -= tmp;
			tmp *= 2;
			if(c[i] < tmp && c[i]){
				w[++num] = c[i] * a[i];
				v[num] = c[i] * b[i];
				id[num] = i;
				break;
			}
		}
	}
}

int main(){
	n = read();
	for(int i = 1; i <= n; i++)
		a[i] = read(), b[i] = read(), c[i] = read();
	m = read();
	prework();
	n = num;
	for(int i = 1; i <= n; i++){				//正着
		for(int j = 0; j <= M; j++)
			f1[i][j] = f1[i - 1][j];
		for(int j = M; j >= w[i]; j--)
			f1[i][j] = max(f1[i][j], f1[i - 1][j - w[i]] + v[i]);
	}
	for(int i = n; i >= 1; i--){				//反着
		for(int j = 0; j <= M; j++)
			f2[i][j] = f2[i + 1][j];
		for(int j = M; j >= w[i]; j--)
			f2[i][j] = max(f2[i][j], f2[i + 1][j - w[i]] + v[i]);
	}
	while(m--){
		int x, V, l = 0, r = n;
		ll ans = 0;
		x = read() + 1, V = read();				//注意编号从0开始
		while(l < n && id[l] < x) l++;			//二进制拆分后物品x被拆成了很多个，要找出左右端点
		while(r > 0 && id[r] > x) r--;
		for(int i = 0; i <= V; i++)
			ans = max(ans, f1[l - 1][i] + f2[r + 1][V - i]);
		printf("%d
", ans);
	}
	return 0;
}

End