【GOJ 2940】分钱

传送门

分析

拿到这道题，一个思路跃然纸上：贪心。

两个指针，一个从前往后扫一遍，另一个相反，看看最大能匹配多少，再把剩余的翻倍平分。

听上去美好，但是时限会超时？

此时看到：

现在，他们已经尽可能的分配得到更多的钱。

忽然想到：这不就是 ( exttt{dp}) 吗？

设有状态 (dp_{i,j}) 表示前 (i) 张前中，使两人相差为 (j) 且没有放到剩余堆的最多的钱；(c_i) 代表第 (i) 张钞票。

(dp_{i,j}) 的初始状态是 (dp_{i-1,j})，即什么事情也不做。

其中一个人既可以拿下 (c_i)，差距变为 (dp_{i,j}+c_i)，也可以把 (c_i) 送给另一个人，差距变为 (dp_{i,j}-c_i)。

注意：差距减小时可能会出现反超，要加上绝对值！

然后根据具体题意输出 ( exttt{sum}-dfrac{{dp}_{i,j}}{2}) 即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=5e5+5;
int a[N],f[N][M];
int main() {
	int n,sum=0;
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d",a+i),sum+=a[i];
	}
	memset(f,-0x3f,sizeof(f)),f[0][0]=0;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=sum; j++) {
			f[i][j]=max(f[i-1][j],f[i-1][j+a[i]]+a[i]);
			f[i][j]=max(f[i][j],f[i-1][abs(j-a[i])]+a[i]);
		}
	}
	printf("%d",sum-f[n][0]/2);
	return 0;
}