zzuli 20级第六次周赛 2733 问题 K: 键盘霸主hrs_zzuli 周赛 6

题目描述

众所周知，hrs学长实力强悍，就没有我hrs不会的题。打比赛的时候经常占着键盘不下来。
队友第一次来借键盘：hrs：“等会儿，这道题我快A了”。 几分钟过后，队友第二次来借键盘：hrs：“慌啥，刚刚题意弄错了，我改下”。
十分钟过后，队友又来催了，hrs：“你在教我做事”

。。。。。。 几分钟后，hrs学长极不情愿地离开他心爱的键盘。
队友成功地摸到了键盘，看着手下熟悉而又陌生的键盘，队友一时间竟不知道该做些什么。就在这时，hrs的声音响起。“给你10分钟写这题，写不完就换我来”，hrs学长太强了，队友苦思冥想两个小时的题，对hrs来说，不过是一眼题罢了。
什么，你说前面有道题说hrs很菜，一眼看不出来。→_→，那道题是他自己出的，那叫谦虚，懂？ 啥，我觉得hrs学长是个cj。
这样，来看看hrs学长的一眼题。 这里有n个小球，每个小球都有一个随机编号。你可以执行以下操作。
从这n个小球挑选出几个小球，将这些小球上面的编号相加，这样我们就得到了一个数字。 令mi为无法通过以上操作得到的最小正整数，输出mi-1。

输入

第一行一个数字T，表示T组测试数据。（0<T≤10） 每组数据有两行输入。 第一行一个整数n，表示小球的个数。（1≤n≤ 10）
第二行n个整数a1，a2，a3，…，an（1≤i≤n，0<ai≤1000），表示小球上面的编号。

输出

输出每组数据的mi-1

样例输入

3
3
1 2 3
3
3 3 3
3
1 1 1

样例输出

6
0
3

动态规划思想， 用数组储存所有的相加可能。

参考代码：

#include<bits/stdc++.h>
using namespace std;

int main() {
	int T;
	cin >> T;
	int dp[10005];
	while(T--) {
		memset(dp, 0, sizeof(dp));
		int n, ans = 0;
		cin >> n;
		int arr[n];
		dp[0] = 1;
		for(int i = 0; i < n; i++) {
			cin>>arr[i];
		}

		for(int i = 0; i < n; i++) {
			for(int j = 10000; j >= 0; j--) {
				if(dp[j] == 1) {
					dp[j+arr[i]] = 1;
				}
			}
		}
		for(int i = 1; i < 10004; i++) {
			if(dp[i] == 0) {
				cout << i-1 << endl;
				break;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

第一次写博客，锻炼一下自己。