题目描述
Kile和Pogi在街上捡到了N张钞票。在确定无法找到失主之后，两人决定将钞票平分。他们想要得到相同数量的钱，所以他们将这些钞票尽可能分成价值相等的两份。但是当钞票无法平分的时候会剩下一些。
由于他们不能将剩余的钞票留在街上，他们决定去附近的赌场并将所有剩下的钞票都押上，希望最终得到两倍的赌注。幸运的是他们真的让赌注翻倍了，于是Kile和Pogi平分了赢的钱。
由于极度兴奋，他们失去了计算能力，请你帮助他们计算出每人带回家了多少钱。
输入
第一行输入包含一个整数N（1≤N≤500）。表示钞票的张数。
接下来N行每行包含一个整数Ci。第i+1行的整数Ci表示第i张钞票的面额。保证N张钞票的总值不超过1e5。
输出
输出一个整数。表示两人分别带回家的钱。
前方高能
解题思路
很明显嘛，DP，然而并不会打。考场搞半天，弄出来一个玄学的，本来暴力可以50，结果又因为绑点，玄学操作搞得1分都没有...
首先考虑三维
dp[i][j][k]表示用前i张钱可不可以令第一个人取j元，第二个人取k元。显然这样弄70分就有了。
显然空间时间要爆炸。
我们再考虑一下。
dp[i][j]表示用前i张钱令两人取的钱的差值为j的取的钱的总和最大值。
有些东西还是自己想会好做一下，
相信dp定义一出来还是很容易推的。
70分：
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n,c[100005],sum;
bool dp[505][1005][1005];
int main(){
//freopen("kas.in","r",stdin);
// freopen("kas.out","w",stdout);
scanf("%d",&n);
for (int i = 1;i <= n;i ++){
scanf ("%d",&c[i]);
sum += c[i];
}
dp[0][0][0] = 1;
for (int i = 1;i <= n;i ++){
for (int j = 0;j <= sum;j ++){
for (int k = 0;k <= sum;k ++){
if (j >= c[i])
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][j - c[i]][k]);
if (k >= c[i])
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][j][k - c[i]]);
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][j][k]);
}
}
}
for (int i = sum;i >= 0;i --){
if (dp[n][i][i]){
printf("%d
",sum - i);
return 0;
}
}
}100分：
这里有一个清空问题，本人是这样理解的。
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n,c[100005],sum;
int dp[505][100005];
int main(){
//freopen("kas.in","r",stdin);
// freopen("kas.out","w",stdout);
scanf("%d",&n);
for (int i = 1;i <= n;i ++){
scanf ("%d",&c[i]);
sum += c[i];
}
memset(dp,-0x3f,sizeof(dp));//这里为何要清负数？因为可能你在转移的时候，有一些DP的值根本没有更新。
//然而你如果仅仅是0，加上c[i]就有可能大于当前DP，因而做出了一个错误的转移
dp[0][0]=0;
for (int i = 1;i <= n;i ++){
for(int j = 0;j <= sum;j ++){
dp[i][j] = dp[i - 1][j];
dp[i][j] = max(dp[i - 1][j + c[i]] + c[i],dp[i][j]);
dp[i][j] = max(dp[i - 1][abs(j - c[i])] + c[i],dp[i][j]);
}
}
printf("%d",sum - dp[n][0] / 2);
}