自动搬运

查看原文

来自洛谷，原作者为

	Getaway_Car fsutil file createnew

搬运于2025-08-24 22:24:11，当前版本为作者最后更新于2025-01-22 16:25:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

鲜花

校内模拟赛T3，赛时想到了正解的 $60\%$，所以就得了 $60$ 分……

赛后 T 了若干发之后终于过了。

---

本文提供一种非回退背包的解法。

在下文中，记 $k = \sum_{i = 1}^n a_i$。

Solution 1

假设我们修改 $a_i$，设用其他数拼出的方案数为 $cnt_i$ ，那么当 $a_i'$ 足够大时，有 ${cnt_i'}_{max} = 2cnt_i + 1$。所以问题就转化到了求 $\max_{i = 1}^{n} cnt_i$ 与 $i$。

考虑枚举 $i$，并对于每个 $i$ 进行 DP 计算 $cnt_i$。求出最大值与最大值位置（即 $p$）后，需要求 $q$。

设 $f_i$ 表示是否能凑出 $i$。很容易发现，当 $\sum_{i = 1}^k [f_i = 1, f_{i + q} = 1] = 0$ 时，$q$ 合法。暴力枚举即可。

时间复杂度 $O(n ^ 2k + k ^ 2)$，完全不能接受。

Solution 2

我们发现，在第一种解法中，对于同一个物品，进行了太多次的背包 DP。我们尝试只进行一次DP，并标记为了凑出当前这个数，有哪些位置必须被选取。若不需要选取第 $i$ 个数，代表当我们修改 $a_i$ 时仍然能凑出这个数。

具体地，设 $dp_{i, j}$ 表示为了凑出 $i$，是否需要 $a_j$。转移方程如下。

$$$ f_i = \mathop{bitor}\limits_{1\le k\le n} f_{i - a_k}\\ \ \\ dp_{i, j}= \mathop{bitand}\limits_{1\le k\le n,\ f_{i - a_k} = 1} \begin{cases} dp_{i - a_k, j}\ (j \ne k)\\ 1\ (j = k) \end{cases} $$$

DP 完之后统计 $cnt_i$，剩余步骤与解法一相同。

时间复杂度仍然是 $O(n ^ 2k + k ^ 2)$，但常数好得多，在洛谷上取得了 $60$ 分的好成绩！（这也是我赛时的做法，个人认为特别符合直觉。）

Solution 3

考虑优化一下求 $q$ 的过程。前文已推得，当 $\sum_{i = 1}^k [f_i, f_{i + q}] \ne 0$，$q$ 不合法。设全集（可重集）为 $U$，此时有可重集 $S, T$ 满足 $S, T \subset U, (\sum_{i \in S} b_i) - (\sum_{i \in T} b_i) = q$。再正反做一次背包即可。总时间复杂度 $O(n^2k)$，还是卡。

Solution 4

由于所有状态都是 $0$ 或 $1$，所以可以用 bitset 优化。最终复杂度 $O(\frac{n ^ 2k}{w})$，趋近于 $O(nk)$，可以通过。

Code

在代码中，dp[i][0] 代表文中的 $f_i$，其余的 dp[i][j] 代表文中的 $dp_{i, j}$。

int n, a[105], sum, cnt[105], mx, p;
bitset<105> dp[700005];
bitset<1400005> tmp;

int main() {
	read(n);
	for(int i = 1; i <= n; ++i)
		read(a[i]), sum += a[i];
	// 初始化 dp 数组
	sort(a + 1, a + 1 + n);
	dp[0] = 1, dp[1][0] = 0;
	for(int i = 1; i <= n; ++i)
		dp[1][i] = 1;
	for(int i = 2; i <= sum; ++i)
		dp[i] = dp[i - 1];
	// 计算 dp 数组
	for(int i = 1; i <= n; ++i)
		for(int j = sum; j >= a[i]; --j)
			if(dp[j - a[i]][0]) {
				dp[j] &= dp[j - a[i]];
				if(!dp[j][0]) dp[j][i] = 1;
				dp[j][0] = 1;
			}
	// 统计 cnt 并计算 p
	for(int i = 1; i <= sum; ++i)
		if(dp[i][0])
			for(int j = 1; j <= n; ++j)
				if(!dp[i][j])
					++cnt[j];
	mx = p = 0;
	for(int i = 1; i <= n; ++i)
		if(cnt[i] > mx) mx = cnt[i], p = i;
	// 计算 q
	tmp[7000 * n] = 1;
	for(int i = 1; i <= n; ++i)
		if(i != p)
			tmp = tmp | (tmp << a[i]) | (tmp >> a[i]);
	for(int i = 1; i <= sum - a[p] + 1; ++i)
		if(!tmp[7000 * n + i])
			return printf("%d %d\n", a[p], i), 0;
}

这代码截止发题解当天竟然还跑出了洛谷最优解。（不过做这道题的人少。）