题解：P10527 [XJTUPC2024] 最后一块石头的重量

hgckythgcfhk · 2024-05-23 20:24:40 · 题解

鉴于大家对题解区现有的唯一一篇题解评价并不好，我决定写一篇详细的题解。

注意到本题是一个背包。

这句话省略了很多东西，感觉和没说一样。

首先先说为什么是个背包，手搓样例 2 可以发现，最优策略并不只是简简单单的大的和小的相互抵消，而是要利用大的和小的操作会使大的减小这个性质进行下一步。

具体的，我给一下样例 2 的解释就很好理解了。

第一次操作：

40 21 ->19

第二次操作：

33 31 ->2

此时，我们剩下的石子的状态是：

2 19 26

然后我们就可以简简单单的用小的消耗大的。

26 19 ->7

7 2 ->5

于是我们发现，我们有时候需要利用一个大的和一个小的制造一个相对中等的，然后用这个中等的去继续操作。

于是，我们不难想到用字母一般化这个过程，推一推式子，~~主要是实在想不出来该干点什么~~。

以 5 个数 a,b,c,d,e 为例，发现顺序不影响结果，于是我们默认有序，即 a\le b\le c\le d\le e。

样例 2 的一般形式相当于：

e,a\to e-a

d,c\to d-c

到这里也许我说的是废话，但是下面就有用了。

b,e-a\to b-(e-a)

b-(e-a),(d-c)\to b-(e-a)-(d-c)

拆开括号：

b-e+a-d+c

这个不好看，换个顺序：

a+b+c-d-e

有没有发现，这些操作下来相当于把所有数分成两组，求两组的差的最小值。

当然这个东西可以用更复杂的例子去验证，自己动手并不麻烦，但会大幅度增加题解的篇幅，所以我不作展示，总是，这个结论的正确性是很好理解的。

于是我就想起来一个题，做法是随机打乱数组，然后用一种正确率还行的贪心，这样进行很多次取最小值，具体这个贪心怎么写不做赘述，感兴趣的看这题。

但是，这个正确率放在本题的数据范围下并不怎么样。

于是想到背包，具体的，状态转移方程如下：

dp_{i+1,j+a_i}\gets dp_{i,j}

dp_{i+1,j-a_i}\gets dp_{i,j}

时间复杂度 O(n\sum a_i) 明显过不了。

于是考虑 bitset 优化，优化需要我们写成一个方便位运算的形式，首先得写成 dp_{i,j}=\dots 的形式，于是整体带换一下，则有：

dp[i]=(dp[i-1]<<a[i])|(dp[i-1]>>a[i])

但是，我们还漏了一种情况，我们可以用新加进来的石子减前面的石子，于是有：

for(int k=0;a[i];--a[i],++k)dp[f][k]=dp[f][k]|dp[f^1][a[i]];

这里加了滚动数组优化，否则会 MLE。

于是可以写出程序。

signed main(){open;int n,a;cin>>n;dp[0][0]=1;
    for(int i=1;i<=n;++i){rg const bool f=i&1;cin>>a;
        dp[f]=(dp[f^1]<<a)|(dp[f^1]>>a);
        for(int k=0;a;--a,++k)dp[f][k]=dp[f][k]|dp[f^1][a];
    }for(int i=0;i<5001;++i)if(dp[n&1][i])return cout<<i,0;
}

这个程序会在 #4 出错，经过我大量实验发现，是因为 bitset 需要开的很大，但是我们开的不够大，正确的做法是随机打乱一下 a 数组，具体很好实现，我就不写了。