IT评测·应用市场-qidao123.com技术社区

标题: 【补题】P10527 [XJTUPC 2024] 末了一块石头的重量 [打印本页]

作者: 忿忿的泥巴坨 时间: 昨天 10:27
标题: 【补题】P10527 [XJTUPC 2024] 末了一块石头的重量
题意：
标题描述

有一堆石头，用整数数组 a 表现。其中 ai 表现第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x≤y。那么粉碎的可能结果如下：

如果 x=y，那么两块石头都会被完全粉碎；
如果 x！=y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y−x。

末了，最多只会剩下一块石头。输出此石头最小的
输入格式

输入数据共两行。
第一行输入一个整数 n (1≤n≤10000)，表现石子的数量；
第二行输入 n 个整数 ai (1≤ai≤5000)，表现第 i 块石头的重量。
可能重量。如果没有石头剩下，就输出 0。

思路：参考10527 - 洛谷专栏题解2：P10527 末了一块石头的重量 - 洛谷专栏
1.首先这道题并不能贪婪，得发现终极的答案就是全部的数，按照某种方式加减，关于想法可以参照给出的两篇题解，表明都非常明了。
可以看作是不同的数字互相减少b-（a-c），导致前面的权值分成正负，形成了两个集合，求集合和的差即可。
那么标题从现在开始就可以转换成背包了
2.背包，dp【i】【j】是填入第i个物品（正负自选）j 重量是否能存在，终极询问全部物品填入后，最小的存在的j重量。但是完全暴力01的时间复杂度O(n*

)包罗空间复杂度，这个时间和空间复杂度是不被接受的。
于是使用了随机化+bitset优化+滚动数组。
表明：
bitset提供了常数的时间复杂度减小，如果你不会bitset - OI Wiki
随机化则是让

减少，因为为了得到最小值，一定是分成+-两组的，这让终极的答案不会到达一个不可接受的空间和时间复杂度。因为数据可能把正号组全部放在前面了，但是随机打乱后，就不会存在这一情况了，时间空间被降到了一个公道的程度。
滚动数组就是因为01背包只要考虑前一状态，剩下的已有状态不会对答案有影响，只要提供两个数组让终极的答案能得出就行了。
随机数感觉非常的玄学啊……
3.状态转移：
bitset优化之后，当前出现的数字变成了某一状态，0/1代表有无。
那么一个数添加正或者添加负，就是dp[i & 1] = (dp[~i & 1] << a) | (dp[~i & 1] >> a);
已经有的状态加上这个数，已经有的状态减去这个数。
但是如果我们真的将正负号都分清楚，空间得开成
的两倍（可能放的都是负的），但是好在其实正负的区别就是绝对值，绝对值就是末了的答案，如许让空间继承缩小了。
因此现在的dp【i】【j】是添加到第i个数，当前剩下的数的绝对值是多少
但是使用绝对值又有标题了，3-5=-2，但是bitset可没有-2，我们也没有偏移bitset

for (int j = a[i]; j > 0;j--)
dp[i & 1][a[i]-j] = dp[i & 1][a[i]-j] | dp[~i & 1][j];
复制代码
实现了手动的绝对值偏移回正，前一状态的3如果存在，-5之后会得到2。
那么至此，整道题应该完整的表明明白了，代码很短，其实主要是神奇的时间空间优化
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
const int N = 2e4 + 10;
const int INF = 1e18;
const int MOD = 998244353;
int a[N];
bitset<(1ll << 20)> dp[2];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n;i++){
cin >> a[i];
}
shuffle(a+1, a + n+1, default_random_engine(time(0)));
dp[0].set(0);
for (int i = 1; i <= n;i++){
dp[i & 1] = (dp[~i & 1] << a[i]) | (dp[~i & 1] >> a[i]);
for (int j = a[i]; j > 0;j--){
dp[i & 1][a[i]-j] = dp[i & 1][a[i]-j] | dp[~i & 1][j];
}
}
for (int i = 0; i < (1 << 20);i++){
if(dp[n&1][i]){
cout << i << endl;
return;
}
}
}
signed main()
{
// IOS;
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4