【题解】P10527 [XJTUPC2024] 最后一块石头的重量
AFewSuns
·
·
题解
背包板子，来水一篇题解。
题目大意
给定一个长度为 n 的数组 a，每次可以选定两个数，若这两个数相同则同时删掉；否则将较小值删掉，然后将较大值修改为它们的差。问最后剩下的数的最小值。
### 题目分析
先进行一些简单的转化。不妨允许存在负数，那么最终每个数的贡献都会是 $+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)$ 的做法，[具体做法在这里](https://www.cnblogs.com/AFewSuns/p/knapsack.html#%E6%9B%B4%E4%BC%98%E7%A7%80%E7%9A%84%E7%BA%BF%E6%80%A7%E8%A7%A3%E6%B3%95)，或者参考 [ABC221G 的题解](https://www.luogu.com.cn/problem/solution/AT_abc221_g)。
具体地，先贪心从前往后选取一段前缀的物品使得他们的和刚好 $\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)$。
---
### 代码
```cpp
#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;
}
}
}
```