| Description | ||
|
DS最近刚学会了背包。比如，给一个序列，问是否存在一个子集满足元素和为 X
xiaodao 觉得 DS |
||
| Input | ||
|
第一行是一个整数 T |
||
| Output | ||
|
对于每组数据，输出一个整数 Y |
||
| Sample Input | ||
3 3 1 2 4 2 2 100000 4 1 2 3 4 |
||
| Sample Output | ||
8 1 11 |
||
| Hint | ||
|
对于第一组样例
对于第三组样例
|
||
| Source | ||
| 哈尔滨理工大学第四届ACM程序设计竞赛（同步赛） |
解题：看了解题报告发现真的好经典。有背包的思想。
只要s+1<a,则s+1就是最小不能组成的数，否则s+=a;
#include<stdio.h>
int main()
{
long long sum,a;
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
int flog=1;
while(n--)
{
scanf("%lld",&a);
if(sum+1<a)flog=0;
if(flog)sum+=a;
}
printf("%lld\n",sum+1);
}
}