UVA - 562 Dividing coins

发布时间:2016-12-11 18:09:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVA - 562 Dividing coins",主要涉及到UVA - 562 Dividing coins方面的内容,对于UVA - 562 Dividing coins感兴趣的同学可以参考一下。

题意:求将硬币分成差最小的两份,输出差值,这题与凑硬币不同的地方是,每个硬币只有一个,所以我们从sum / 2 开始凑#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 110; int arr[MAXN],dp[MAXN*550]; int n; int main(){ int t; scanf("%d",&t); while (t--){ memset(dp,0,sizeof(dp)); int sum = 0; scanf("%d",&n); for (int i = 0; i < n; i++) { scanf("%d",&arr[i]); sum += arr[i]; } dp[0] = 1; for (int i = 0; i < n; i++){ for (int j = sum / 2; j >= arr[i]; j--) if (dp[j - arr[i]]) dp[j] = 1; } int ans = sum / 2; while (ans >= 0 && dp[ans] == 0) ans--; ans = sum - 2 * ans; printf("%d\n",ans); } return 0; }

上一篇:cookie加密解密
下一篇:回溯法解决N皇后问题

相关文章

相关评论