本文主要是介绍NYOJ 456 邮票分你一半，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目 ： http://acm.nyist.net/JudgeOnline/problem.php?pid=456
描述
- 输入
- 第一行只有一个整数m（m<=1000),表示测试数据组数。
接下来有一个整数n(n<=1000)，表示邮票的张数。
然后有n个整数Vi(Vi<=100)，表示第i张邮票的分值。 输出 - 输出差值，每组输出占一行。 样例输入
-
2 5 2 6 5 8 9 3 2 1 5
样例输出 -
0 2
bool dp[50005]; int x[1002]; int main() {int n;cin >> n;int m;while(n--){scanf("%d",&m);int sum = 0,ans = 0;for(int i = 0;i < m;i++){scanf("%d",&x[i]);sum += x[i];}memset(dp , 0 , (sum + 2)*sizeof(bool));dp[0] = 1;for(int i = 0;i < m;i++){for(int j = (sum>>1);j >= x[i];j--){dp[j] |= dp[j - x[i]];}}for(int i = (sum>>1);i >= 0;i--){if(dp[i]){ans = sum - (i<<1);break;}}printf("%d\n",ans);}return 0; }
这篇关于NYOJ 456 邮票分你一半的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
