自动搬运

查看原文

来自洛谷，原作者为

	AFewSuns 弱省弱校蒟蒻，tcl，zbl

搬运于2025-08-24 22:58:53，当前版本为作者最后更新于2024-05-23 20:06:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

背包板子，来水一篇题解。

题目大意

给定一个长度为 $n$ 的数组 $a$，每次可以选定两个数，若这两个数相同则同时删掉；否则将较小值删掉，然后将较大值修改为它们的差。问最后剩下的数的最小值。

$1 \leq n \leq 10000,1 \leq a_i \leq 5000$。

题目分析

先进行一些简单的转化。不妨允许存在负数，那么最终每个数的贡献都会是 $+1$ 或 $-1$，需要最小化的则是最后的和的绝对值。

具体而言，我们的操作可以看作是每次选择一个数 $y$ 去跟当前的数 $x$ 进行“抵消”。若 $x>0$ 则将 $x$ 减去 $y$；若 $x \leq 0$ 则将 $x$ 加上 $y$。

这乍一看会有加入顺序导致的 $\pm 1$ 限制，但其实我们完全可以将它看成任意选取 $\pm 1$ 的系数后最小化和的绝对值。这是为什么呢？

设 $S_{+}$ 为选取 $+1$ 的数的集合，$S_{-}$ 为选取 $-1$ 的数的集合，那么可以在当前数 $>0$ 的时候选取 $S_{-}$ 内的数进行减法，在当前数 $\leq 0$ 的时候选取 $S_{+}$ 内的数进行加法，就完全符合操作的限制了。

如果最后发现某个集合空了，不妨假设是 $S_{-}$ 空了，那么在当前 $>0$ 的时候就不得不使用 $S_{+}$ 的数了。但这显然不优，因为把这些数的系数换成 $-1$ 即可使得最后的绝对值减小。

设 $sum=\sum\limits_{i=1}^{n}{a_i}$，将整体加上 $sum$ 再除以二就变成了 $01$ 背包问题，需要在和 $\leq \frac{sum}{2}$ 的同时最大化和。

设 $a_i$ 最大值为 $V$，minstdfx 的做法是随机打乱后 bitset 优化 01 背包 $\mathcal O(\frac{n\sqrt{n}V}{\omega})$。

实际上有 $\mathcal O(nV)$ 的做法，具体做法在这里，或者参考 ABC221G 的题解。

具体地，先贪心从前往后选取一段前缀的物品使得他们的和刚好 $\leq \frac{sum}{2}$，设选取的前缀为 $[1,pos]$，然后将序列分为 $\leq pos$ 和 $> pos$ 两部分。

考察最后选取的物品，一定是从当前的状态下，删去 $\leq pos$ 的一些物品，再加上 $>pos$ 的一些物品得到的。注意到可以通过合理安排顺序使得过程中的和始终在 $(\frac{sum}{2}-V,\frac{sum}{2}+V]$ 中间。

于是设 $f_{r,w}$ 表示最大的 $l$，使得仅操作 $[l,r]$ 内的数可以凑成 $w$。这里操作指的是删去 $[l,pos]$ 中的数或加入 $(pos,r]$ 中的数。

转移分为三类：

• $f_{r,w} \leftarrow f_{r-1,w}$，即从 $r-1$ 转移过来且不操作 $r$；

• $f_{r,w+a_r} \leftarrow f_{r-1,w}(w \leq \frac{sum}{2})$，即从 $r-1$ 转移过来且操作 $r$；

• $f_{r,w-a_l} \leftarrow l(w > \frac{sum}{2},l < f_{r,w})$，即从左边转移过来且操作 $l$。

注意第三步转移中，若 $l<f_{r-1,w}$，那么这种情况会在 $r-1$ 时被转移（之后通过第一步转移回来），所以只需要转移 $l \geq f_{r-1,w}$ 的部分，单次转移复杂度是 $\mathcal O(f_{r,w}-f_{r-1,w})$，所以总的复杂度是对的。由于第二维的范围在 $(\frac{sum}{2}-V,\frac{sum}{2}+V]$ 内，是 $\mathcal O(V)$ 的，所以总时间复杂度为 $\mathcal O(nV)$。

代码

#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
ll n,m,all=0,V=5000,a[10010],f[2][10010];
int main(){
	n=read();
	fr(i,1,n) a[i]=read();
	fr(i,1,n) all+=a[i];
	m=all/2;
	ll pos=0,sum=0;
	while(pos<n&&(sum+a[pos+1])<=m){
		pos++;
		sum+=a[pos];
	}
	f[pos&1][sum-m+V]=pos+1;
	fr(i,pos+1,n){
		ll o=i&1;
		fr(j,1,2*V) f[o][j]=0;
		fr(j,1,2*V) f[o][j]=max(f[o][j],f[o^1][j]);
		fr(j,1,V) f[o][j+a[i]]=max(f[o][j+a[i]],f[o^1][j]);
		pfr(j,2*V,V+1) fr(k,f[o^1][j],f[o][j]-1) f[o][j-a[k]]=max(f[o][j-a[k]],k);
	}
	pfr(i,V,1){
		if(f[n&1][i]){
			write(all-2*(m+i-V));
			return 0;
		}
	}
}