BalticOI 2022 D1T3 Uplifting Excursion 题解

First Post:

Last Update:

感觉今年的 BalticOI 较为简单（除通信题）。就 2022 年这套题来说，是有训练价值的，但并没有非常难的题。

题意传送门： https://loj.ac/p/3776

注意到这题要我们做个类似背包的东西，但是所有物品价值为 ，体积不大，个数很多。

先说 的情况。

看到这种目标体积远大于单个物品体积的题，容易想到先用贪心尝试逼近那个目标体积。在贪心时，我们显然倾向于选体积更小的物品，这样能选的物品更多。贪心时在不超过 的前提下，选尽可能多的物品。贪心完之后， 会剩余一个不超过 的部分。

在贪心解的基础上，我们考虑用 DP 凑出这个剩余部分。此时有一部分物品要新增，有一部分已经选的物品要撤销，我们称这种过程为调整。我们可以证明，调整的总次数不超过 。

证明：我们可以贪心地排列调整的顺序，使得调整序列中每处的前缀和都在 之间，而如果序列中有两个位置前缀和相同，那么这中间的所有操作都是无意义的。所以序列中每个位置的前缀和互不相同，所以序列长度不超过 。

因此，调整的物品的总体积是 级别的。我们可以用 两个背包分别记录新增和撤销体积为某个值时的最大价值（将撤销一个物品的价值看作 ）。这两个背包都是多重背包，可以用二进制分组的技巧，在 的时间内求出这两个背包。统计答案是容易的。

上文假设没有体积为负的物品，实际上有体积为负的物品也区别不大。我们可以将体积为负的物品强制选取，然后再尝试撤销这些物品。这样所有物品的体积和 就都是正的了，如上文的办法跑贪心和背包即可。

于是本题就做完了，时间复杂度 。愿意的话可以做到 。

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
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool ckmin(T &x,const T &y) { return (x > y) && (x = y,true);}
template<typename T> inline bool ckmax(T &x,const T &y) { return (x < y) && (x = y,true);}

const int N = 3e2 + 5;
typedef long long ll;
int m,lim;
ll L;
ll au[N],ad[N],bu[N],bd[N];
int A[N * N * 2],B[N * N * 2]; // A 相当于体积为正，B 相当于体积为负
inline void ins(int *A,int v,int w,ll num) { // 统一 ckmax，反悔背包的价值取反
	for(ll t = 1;t <= num;t <<= 1) {
		for(int i = lim;i >= t * v;i--)
			ckmax(A[i],A[i - t * v] + (int)t * w);
		num -= t;
	}
	if(num >= 1)
		for(int i = lim;i >= 1ll * num * v;i--)
			ckmax(A[i],A[i - num * v] + (int)num * w);
}
int main() {
	cin >> m >> L;
	for(int i = m;i >= 1;i--) cin >> ad[i];
	ll num; cin >> num;
	for(int i = 1;i <= m;i++) cin >> au[i];
	lim = m * m;
	for(int i = 1;i <= m;i++) num += ad[i],L += 1ll * i * ad[i];
	if(L < 0) return puts("impossible"),0;
	for(int i = 1;i <= m;i++) {
		if(au[i] * i <= L) { num += (bu[i] = au[i]);L -= 1ll * i * bu[i];}
		else { num += (bu[i] = L / i);L -= 1ll * i * bu[i];break;}
	}
	for(int i = m;i >= 1;i--) { // 体积为负的物品，先强制选再反悔
		if(ad[i] * i <= L) { num -= (bd[i] = ad[i]);L -= 1ll * i * bd[i];}
		else { num -= (bd[i] = L / i);L -= 1ll * i * bd[i];break;}
	}
	memset(A,-0x3f,sizeof A);memset(B,-0x3f,sizeof B);
	A[0] = B[0] = 0;
	for(int i = 1;i <= m;i++) {
		if(au[i] - bu[i]) // 多选体积为正的
			ins(A,i,1,au[i] - bu[i]);
		if(bu[i]) 
			ins(B,i,-1,bu[i]);
		if(ad[i] - bd[i]) // 多反悔
			ins(A,i,-1,ad[i] - bd[i]);
		if(bd[i])
			ins(B,i,1,bd[i]);
	}
	ll ans = -1;
	for(int j = 0;j + L <= lim;j++)
		if(B[j] > -1e9 && A[j + L] > -1e9)
			ans = max(ans,num + B[j] + A[j + L]);
	if(ans < 0) puts("impossible");
	else cout << ans << endl;
	return 0;
}
/*
3 10
0 0 0 2 4 2 1
*/
≡