hrbust2090背包(经典。。，想不到就有点难)

本文主要是介绍hrbust2090背包(经典。。，想不到就有点难)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

DS最近刚学会了背包。比如，给一个序列，问是否存在一个子集满足元素和为 X ， DS 会用一种方法：

int dp[X+1];

dp[0] = 1;

for (int i = 0 ;i < n ; ++i)

for (int j = 0 ; j < X ; ++j)

if (dp[j] && j+a[i] <= X) dp[j + a[i]] = 1;

return dp[X];

xiaodao 觉得 DS 非常聪明，不过她想难为一下DS。她给了DS一个序列，序列中有 N（N ≤10⁷）个正整数，满足1≤A1 ,Ai≤Ai+1 ,Ai≤10⁹
然后她让DS求这个序列的 “最小不可构造数”，也就是最小的 Y 使得 Y 不能表示为序列的某个子集中所有元素的和。

Input

第一行是一个整数 T 代表数据组数，以下是 T 组数据。
每组数据第一行一个整数 N 代表本组数据一共有 N 个整数。
第二行 N 个整数 Ai 满足 1≤A1 ,Ai≤Ai+1 ,Ai≤10⁹
所有的 N 加起来的和小于 10⁷

Output

对于每组数据，输出一个整数 Y 代表本组数据的最小不可构造数。

Sample Input

Sample Output

8
1
11

Hint

对于第一组样例

1 = 1 , 2 = 2 , 3 = 1 + 2 , 4 = 4 , 5 = 1 + 4 , 6 = 2 + 4 , 7 = 1 + 2 + 4

对于第三组样例

1 = 1 , 2 = 2 , 3 = 1 + 2 = 3 , 4 = 4 = 1 + 3 , 5 = 1 + 4 = 2 + 3 , 6 = 2 + 4 = 1 + 2 + 3 , 7 = 1 + 2 + 4 , 8 = 1 + 3 + 4 , 9 = 2 + 3 + 4 , 10 = 1 + 2 + 3 + 4

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);}
}

这篇关于hrbust2090背包(经典。。，想不到就有点难)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！