题目描述
Kile和Pogi在街上捡到了N张钞票。在确定无法找到失主之后，两人决定将钞票平分。他们想要得到相同数量的钱，所以他们将这些钞票尽可能分成价值相等的两份。但是当钞票无法平分的时候会剩下一些。
由于他们不能将剩余的钞票留在街上，他们决定去附近的赌场并将所有剩下的钞票都押上，希望最终得到两倍的赌注。幸运的是他们真的让赌注翻倍了，于是Kile和Pogi平分了赢的钱。
由于极度兴奋，他们失去了计算能力，请你帮助他们计算出每人带回家了多少钱。
输入格式
第一行输入包含一个整数N（1≤N≤500）。表示钞票的张数。
接下来N行每行包含一个整数Ci。第i+1行的整数Ci表示第i张钞票的面额。保证N张钞票的总值不超过1e5。
输出格式
输出一个整数。表示两人分别带回家的钱。
样例
样例输入1
4 2 3 1 6
讯享网样例输出1
讯享网6样例输入2
5 3 2 5 8 13样例输出2
讯享网18数据范围与提示
对于50%的数据，N≤13。
对于70%的数据，N≤50，并且钞票的总值不超过1000。
思路详解
DP好题
dp[i][j] 表示前i张前中，使两人相差为 j 且没有放到剩余堆的最多的钱
dp[i][j] = dp[i-1][j] 把第i张钱放到剩余那堆里
dp[i][j] = dp[i-1][j+c[i]]+c[i] 把第i张钱给当前钱少的，差距由j+c[i]缩小到 j
dp[i][j] = dp[i-1][abs(j-c[i])] 把第i张钱给当前钱多的，当前钱多的有2种可能，之前就比钱少的多或拿到第i张钱后反超回来
Emm。。。差不多就这样吧
代码
理解消化推DP式的思路。。。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <algorithm> using namespace std; int n , c[505] , sum , ans ; int dp[505][] ; //dp[i][j] 表示前i张前中，使两人相差为 j 且没有放到剩余堆的最多的钱 //dp[i][j] = dp[i-1][j] 把第i张钱放到剩余那堆里 //dp[i][j] = dp[i-1][j+c[i]]+c[i] 把第i张钱给当前钱少的，差距由j+c[i]缩小到j //dp[i][j] = dp[i-1][abs(j-c[i])] 把第i张钱给当前钱多的 //当前钱多的有2种可能，之前就比钱少的多或拿到第i张钱后反超回来 int main() { scanf("%d", &n ); for( int i = 1 ; i <= n ; ++ i ) { scanf("%d", &c[i] ); sum += c[i] ; } memset( dp , -0x3f , sizeof(dp) );//赋为极大负值，因为dp[i][j]表示的为差距 dp[0][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][j] , max( dp[i-1][j+c[i]]+c[i] , dp[i-1][abs(j-c[i])]+c[i] ) ); } } ans = sum-dp[n][0]/2 ; printf("%d", ans ); }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/126274.html