BZOJ 3163 [Heoi2013]Eden的新背包问题

Posted on

题解

这道题第一眼看是维护前缀后缀然后合并的，但是这样复杂度很高，据说可以水过

因此，不考虑合并。那么问题就是去掉每一个物品，做一次多重背包。这样的复杂度为\(O(n^2m)\)。

考虑以上算法的重复计算部分。可以发现有许多是重复计算了的。那么就可以考虑分治，因为分治可以省去许多重复计算。那么算法就显而易见了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <algorithm>
#include <vector>

long long read()
{
	char last = '+', ch = getchar();
	while (ch < '0' || ch > '9') last = ch, ch = getchar();
	long long tmp = 0;
	while (ch >= '0' && ch <= '9') tmp = tmp * 10 + ch - 48, ch = getchar();
	if (last == '-') tmp = -tmp;
	return tmp;
}

const int _n = 1000 + 10, _m = 1000 + 10, _q = 300000 + 10;
int n, q;
int c[_n], v[_n], m[_n];
int que[_m], val[_m];
int f[20][_n];
std::vector<std::pair<int, int> > vec[_n];
int ans[_q];

void update(int *f, int pos)
{
	for (int i = 0; i < c[pos]; i++)
	{
		int head = 1, tail = 1;
		que[1] = 0;
		val[1] = f[i];
		for (int j = 1; i + c[pos] * j <= 1000; j++)
		{
			while (head <= tail && j - que[head] > m[pos])
			{
				head++;
			}
			while (head <= tail && f[i + c[pos] * j] >= val[tail] + (j - que[tail]) * v[pos])
			{
				tail--;
			}
			tail++;
			que[tail] = j;
			val[tail] = f[i + c[pos] * j];
			f[i + c[pos] * j] = val[head] + (j - que[head]) * v[pos];
		}
	}
}

void solve(int l, int r, int d)
{
	if (l == r)
	{
		for (int i = 0; i < (int)vec[l].size(); i++)
		{
			ans[vec[l][i].second] = f[d][vec[l][i].first];
		}
		return;
	}
	int mid = (l + r) >> 1;
	for (int i = 0; i <= 1000; i++)
	{
		f[d + 1][i] = f[d][i];
	}
	for (int i = mid + 1; i <= r; i++)
	{
		update(f[d + 1], i);
	}
	solve(l, mid, d + 1);
	for (int i = 0; i <= 1000; i++)
	{
		f[d + 1][i] = f[d][i];
	}
	for (int i = l; i <= mid; i++)
	{
		update(f[d + 1], i);
	}
	solve(mid + 1, r, d + 1);
}

int main()
{
	n = read();
	for (int i = 1; i <= n; i++)
	{
		c[i] = read();
		v[i] = read();
		m[i] = read();
	}
	q = read();
	for (int i = 1; i <= q; i++)
	{
		int pos, sum;
		pos = read();
		sum = read();
		pos++;
		vec[pos].push_back(std::make_pair(sum, i));
	}
	solve(1, n, 1);
	for (int i = 1; i <= q; i++)
	{
		printf("%d\n", ans[i]);
	}
	return 0;
}