自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:30:48，当前版本为作者最后更新于2022-07-17 21:03:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

题目传送门！

更好的阅读体验？

比赛时考到了这一题，于是写一篇题解纪念一下。

思路

设 $dp_{i, j}$ 表示前 $i$ 张钞票分给两人，两人差尽可能接近 $j$ 的情况下，获得的总钱数。此时不考虑赌场操作。

显然可以分三种情况讨论：

• 不用第 $i$ 张钞票：即 $dp_{i-1, j}$。
• 把第 $i$ 张钞票给第一个人：显然为 $dp_{i-1, |j - a_i|} + a_i$ ，其中 $|x|$ 表示 $x$ 的绝对值。
• 把第 $i$ 张钞票给第二个人：同理，是 $dp_{i-1, j + a_i}$。

因此，状态转移方程为：

$$dp_{i, j} = \begin{cases}dp_{i-1, j}\\dp_{i-1, |j - a_i|} + a_i\\dp_{i-1, j + a_i}\end{cases} $$

重点代码如下。这里加了滚动数组的空间优化。

int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) sum += a[i];
//求最大值，就赋值无穷小。注意 dp[0] = 0。
for (int i = 1; i <= sum; i++) dp[i] = -2147483647; 
for (int i = 1; i <= n; i++) //dp[i] 是主动规数组，tdp[i] 是滚动数组。
{
	for (int j = 0; j <= sum; j++) tdp[j] = max(max(dp[abs(j - a[i])], dp[j + a[i]]) + a[i], dp[j]);	
	for (int j = 0; j <= sum; j++) dp[j] = tdp[j]; //复制进主数组里。
}

那么，两人平均分到 $\left\lfloor dp_{n, 0} \div 2\right\rfloor$ 的钱，剩下 $\Big(\small sum - \left\lfloor dp_{n, 0} \div 2\right\rfloor\Big)$ 的钱去赌场。返回双倍钱，则两人都分得 $\Big(\small sum - \left\lfloor dp_{n, 0} \div 2\right\rfloor\Big)$ 这些钱。

printf("%d", sum - dp[0] / 2);

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 505, M = 2e5 + 5;
int a[N], dp[M], tdp[M];
int main()
{
	int n, sum = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) sum += a[i];
	//求最大值，就赋值无穷小。注意 dp[0] = 0。
	for (int i = 1; i <= sum; i++) dp[i] = -2147483647; 
	for (int i = 1; i <= n; i++) //dp[i] 是主动规数组，tdp[i] 是滚动数组。
	{
		for (int j = 0; j <= sum; j++) tdp[j] = max(max(dp[abs(j - a[i])], dp[j + a[i]]) + a[i], dp[j]);	
		for (int j = 0; j <= sum; j++) dp[j] = tdp[j]; //复制进主数组里。
	}
	printf("%d", sum - dp[0] / 2);
	return 0;
}

希望能帮助到大家！