题意:给你一些硬币,求出分成两堆,使得两堆的差最小,求出差。
用dp[]表示能否分到这么多钱,由于一种分法就是一堆空一堆总和,所以dp[0]一定为true,然后的思想就是如果dp[j - coin[i]]可以分到,那dp[j]肯定能分到。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 562.cpp
* Create Date: 2013-09-21 20:24:49
* Descripton: dp
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 101000;
int a[MAXN];
bool dp[MAXN];
int main() {
int t, n, sum;
scanf("%d", &t);
while (t--) {
memset(dp, 0, sizeof(dp));
sum = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = sum; j >= a[i]; j--)
if (dp[j - a[i]])
dp[j] = 1;
for (int i = sum / 2; i >= 0; i++)
if (dp[i]) {
printf("%d\n", abs(sum - 2 * i));
break;
}
}
return 0;
}
分享到:
相关推荐
Simple Dividing Number Game using JavaScript with Free Source Code
Pku acm 第1014题 Dividing c代码,有详细的注释,动态规划
Matlab Tutorial - 39 - Multiplying and Dividing Matrices Element-by-Element
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
Attachment B Models for Dividing Fractions 附件 B 分数除法模型.doc
研究关于将一个矩形分割为多个矩形的论文,来自路易斯安那州立大学数学系,亦可从作者的个人主页上下载: www.math.lsu.edu/~verrill/research/rectangles.pdf
杭电OJ(1000-1099) AC 代码
a high linearized photonic mixer based on unsymmetrical power dividing for ROF system
基于空分复用弹性光网络的路由与资源分配算法,王晨戈,尹珊,随着互联网技术的发展与各种新应用的出现,需要的网络容量快速增长。而传统的单模光纤的传输容量已经逼近极限,基于空分复用(Spa
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
$ git clone https://github.com/Alladin9393/Search-For-Dividing-Circle.git && cd Search-For-Dividing-Circle $ virtualenv venv -p python3 && source venv/bin/activate $ pip3 install -r requirements.txt ...
Dividing-by-the-number-11:查找要添加到一个数字的数字,以便将输入的数字除以11
html事件改变矩形大小源码 区域1 <div id="dividing-line1"> 区域2 <div id="dividing-line2"> 区域3 </template>
The.Definitive.Guide.to.SWT.and.JFace.eBook-LiB [SWT/JFace开发指南]
1149 Dividing up 经典题,可以用1366的方法做,利用问题的特殊性用贪心做出来 1222 Just the Facts 经典题,据说可能有O(logn)的做法,但我没想到:( 1475 Ranklist 没有完美解决,不知道您有没有好方法…… 1572 ...
The impact factor of a journal is calculated by dividing the number of current year citations to the source items published in that journal during the previous two years. It is an independent measure...
QGridLayout lays out widgets in cells by dividing the available space into rows and columns. QFormLayout, on the other hand, sets its children in a two-column form with labels in the left column and ...
This guide to thesis writing gives some simple and practical advice on the problems of getting started, getting organized, dividing the huge task into less formidable pieces and working on those ...
Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku acm 1014 Dividing Pku acm 1050 To the Max Pku acm 1088 滑雪 Pku acm 2533 Longest Ordered ...
YAFFS is a log-structured ...is determined by dividing the file position by the chunk size. Each chunk has a number of valid bytes, which equals the page size for all except the last chunk in a file.