P8392 Uplifting Excursion

$\mathrm{Description}$

有 $2m+1$ 种物品，重量分别为 $-m,-m+1,\dots ,m-1,m$。重量为 $i$ 的物品有 $a_i$ 个。

你需要拿走若干物品，使得这些物品重量之和恰好为 $l$。在此基础上，你需要拿尽可能多的物品。

问在物品重量之和恰好为 $l$ 的基础上，你最多能拿多少物品。

$\mathrm{Solution}$

$\mathrm{Brute}\mathrm{Force}$（暴力）

当 $m,a$ 比较小的时候，$L$ 最大为 $\sum _{i=1}^m{a}_i$，那么可以考虑直接使用多重背包进行求解。

众所周知，多重背包有 $2$ 种优化方式：二进制优化；单调队列

时间复杂度分别为 $O(nw\log c)$，$O(nw)$。其中，$n$ 为物品种数，$w$ 为最大容量，$c$ 为物品数量。

$\mathrm{Faster}\mathrm{Way}$

当 $a$ 的数量级攀升至 $10^{12}$ 级别，那么 $L$ 的范围就会非常大，故肯定要通过一些操作使得价值的范围缩小。

可以考虑贪心，想要使得范围缩小，且还要最优。一个直观的想法为将选择的重量之和的范围缩小至 $[l-m,l]$，因为 $1$ 次最多加 $m$，所以显然可以控制在该范围内。

那么，如何做是最优的呢？

肯定要先把所有的负数加入，然后考虑单价，贪心选择的物品单价是由高到低的，所以计算一下单价：

• 对于 $i<0$，即重量为负值，由于已经选过，所以再选就等同于删掉，即物品重量会增加 $-i$，数量会减少 $1$，故单价 $=-\frac{1}{-i}$。
• 对于 $i>0$，即重量为正值，由于未曾选过，所以再选物品重量会增加 $i$，数量会增加 $1$，故单价 $=\frac{1}{i}$

那么，单价由高向低排列重量选择顺序为：$1,2,\dots ,m-1,m,-m,-m+1,\dots ,-1$

这样，就可以计算出重量之和在 $[l-m,l]$ 之间的 $1$ 种方案了~~~

int Sum = 0;
for (int i = 0; i <= M; i ++) //先将全部负数加入
    Sum += A[i] * (i - M), Cnt[i] = A[i]; //Cnt 维护用了多少个（具体为什么，后面会说）
for (int i = M + 1; i <= 2 * M; i ++) //按 1,2,...,m 的顺序依次考虑
{
    int num = min((L - Sum) / (i - M), A[i]); //如果再加 A[i] 个就超过 L 了，那么就加到 (L - Sum) / (i - M)，即要使和小于等于 L，最多还能加多少
    Sum += num * (i - M), Cnt[i] = num;
}
for (int i = 0; i < M; i ++) //按 -m,-m+1,...,-1 的顺序依次考虑
{
    int num = min((L - Sum) / (M - i), A[i]); //与上文类似
    Sum += num * (M - i), Cnt[i] -= num;
}

大家可能会问了，这样还是有可能会加很多，然后再减回来呀？这样你背包容积不就又很大了吗？

确实是这样，不过这里有一个性质，后面背包调整到 $l$ 的过程最多操作 $2m+1$ 次。

$\mathrm{Proof}:$

一定有一种方法使得在调整途中一定是在 $[l-m,l+m]$ 之间的，因为 $1$ 次最多加 $m$，或减 $m$，一定存在一种方式使得是在该区间 $[l-m,l+m]$ 的。

那么，最优调整途中会不会出现 $2$ 次相同的重量，一定不会。

可以考虑反证法，假设重量之和在调整途中的变化为：$W_1\to W_2\to W_3\to W_4\dots$

若，$W_2=W_4$ 了，那么考虑 $2\to 4$ 途中如果 加入的数 比 抛弃的数 多，那么由于是基于贪心的最优策略进行的 DP，所以不可能存在加入的数更多的情况，如果存在，贪心的时候就会加进去了，故该情况不成立。反之，如果 $2\to 4$ 途中 加入的数 比 抛弃的数 少，那么此时数的个数还不如 $2$ 时刻的多，重量又没变，那还要 $3\to 4$ 这个过程有什么用呢？

故，与假设矛盾，证毕

---

那么，背包 DP 的时候，对于每种物品，维护最多可以加入多少个，可以抛弃多少个，之后用二进制分组或单调队列优化即可。

所以，存在一种调整最多操作 $2m+1$ 次，所以最多加减 $m^2$ 个重量。所以背包的容积是 $O(m^2)$ 级别的，物品种数是 $O(m)$ 级别的，如果用单调队列优化多重背包的话，那么时间复杂度为 $O(m^3)$，如果用二进制优化，会多个 $\log$，都是可以通过本题的。

int Use = 0;
for (int i = 0; i <= 2 * M; i ++) //已经选择的数量
    Use += Cnt[i];

for (int i = 0; i <= 2 * M; i ++) //二进制分组
{
    if (i == M) continue;
    int k = 1, s = min(A[i] - Cnt[i], M * M); //还能再加入的数量
    while (k <= s)
    {
        w[ ++ idx] = (i - M) * k, v[idx] = k;
        s -= k, k *= 2;
    }
    if (s > 0) w[ ++ idx] = (i - M) * s, v[idx] = s;
    k = 1, s = min(Cnt[i], M * M); //可以抛弃的数量，也就是当前选择的数量
    while (k <= s)
    {
        w[ ++ idx] = -(i - M) * k, v[idx] = -k; //都要加符号，表示抛弃
        s -= k, k *= 2;
    }
    if (s > 0) w[ ++ idx] = -(i - M) * s, v[idx] = -s;
}
//由于空间不太够，所以采用滚动数组优化，注意不能只开 1 维，因为本题既有负的权值，又有正的，无法通过更改枚举顺序来进行滚动数组
memset(F, -0x3f, sizeof F);
F[0][B] = 0;
for (int i = 1; i <= idx; i ++)
    for (int j = B + M * M; j >= 0; j --)
    {
        F[i & 1][j] = F[(i - 1) & 1][j];
        if (j >= w[i] && j - w[i] <= B + M * M) F[i & 1][j] = max(F[i & 1][j], F[(i - 1) & 1][j - w[i]] + v[i]);
    }

if (F[idx & 1][B + L - Sum] + Use < -INF) puts("impossible");
else cout << F[idx & 1][B + L - Sum] + Use << endl;

---

$\mathrm{Accepted}\mathrm{Code}$

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 3e2 + 10, B = 9e4, INF = 1e9;

int M, L;
int A[SIZE * 2], Cnt[SIZE * 2];
int F[2][SIZE * SIZE + B];
int w[SIZE * SIZE], v[SIZE * SIZE], idx;

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> M >> L;

	for (int i = 0; i <= 2 * M; i ++)
		cin >> A[i];

	int Sum = 0;
	for (int i = 0; i <= M; i ++)
		Sum += A[i] * (i - M), Cnt[i] = A[i];
	for (int i = M + 1; i <= 2 * M; i ++)
	{
		int num = min((L - Sum) / (i - M), A[i]);
		Sum += num * (i - M), Cnt[i] = num;
	}
	for (int i = 0; i < M; i ++)
	{
		int num = min((L - Sum) / (M - i), A[i]);
		Sum += num * (M - i), Cnt[i] -= num;
	}

	if (L - Sum > M)
	{
		puts("impossible");
		return 0;
	}

	int Use = 0;
	for (int i = 0; i <= 2 * M; i ++)
		Use += Cnt[i];

	for (int i = 0; i <= 2 * M; i ++)
	{
		if (i == M) continue;
		int k = 1, s = min(A[i] - Cnt[i], M * M);
		while (k <= s)
		{
			w[ ++ idx] = (i - M) * k, v[idx] = k;
			s -= k, k *= 2;
		}
		if (s > 0) w[ ++ idx] = (i - M) * s, v[idx] = s;
		k = 1, s = min(Cnt[i], M * M);
		while (k <= s)
		{
			w[ ++ idx] = -(i - M) * k, v[idx] = -k;
			s -= k, k *= 2;
		}
		if (s > 0) w[ ++ idx] = -(i - M) * s, v[idx] = -s;
	}

	memset(F, -0x3f, sizeof F);
	F[0][B] = 0;
	for (int i = 1; i <= idx; i ++)
		for (int j = B + M * M; j >= 0; j --)
		{
			F[i & 1][j] = F[(i - 1) & 1][j];
			if (j >= w[i] && j - w[i] <= B + M * M) F[i & 1][j] = max(F[i & 1][j], F[(i - 1) & 1][j - w[i]] + v[i]);
		}

	if (F[idx & 1][B + L - Sum] + Use < -INF) puts("impossible");
	else cout << F[idx & 1][B + L - Sum] + Use << endl;

	return 0;
}