链接：https://ac.nowcoder.com/acm/contest/24213/1022
来源：牛客网

题目描述

Listening to the music is relax, but for obsessive(强迫症), it may be unbearable.
HH is an obsessive, he only start to listen to music at 12:00:00, and he will never stop unless the song he is listening ends at integral points (both minute and second are 0 ), that is, he can stop listen at 13:00:00 or 14:00:00,but he can't stop at 13:01:03 or 13:01:00, since 13:01:03 and 13:01：00 are not an integer hour time.
Now give you the length of some songs, tell HH whether it's possible to choose some songs so he can stop listen at an integral point, or tell him it's impossible.
Every song can be chosen at most once.

输入描述: 

		

			The first line contains an positive integer T(1≤T≤60), represents there are T test cases. 
		


		

			For each test case: 
		


		

			The first line contains an integer n(1≤n≤105), indicating there are n songs. 
		


		

			The second line contains n integers a1,a2…an (1≤ai≤109 ), the ith integer ai indicates the ith song lasts ai seconds.

输出描述: 

For each test case, output one line "YES" (without quotes) if HH is possible to stop listen at an integral point, and "NO" (without quotes) otherwise.

题型：

动态规划--选或不选问题--求特定组合是否存在

思路：

1.明确总问题--从n个数中选取i个数，使得其累加值为3600的倍数
2.明确子问题--从i个数中选取j个数，使得其累加值为3600的倍数的方案是否存在
3.明确dp含义--设dp[i][j]为从i个数中选取j个数，使得其累加值为3600的倍数的方案是否存在，存在为1，不存在为0-->（变成一维数组）dp[j]为从i个数中选取j个数，使得其累加值为3600的倍数的方案是否存在，存在为1，不存在为0
4.明确状态转移方程--dp[(j+a[i])%3600]=dp[j]（注意：这里不能够直接这样写，要先用一个vector记录(j+a[i])%3600（当dp[j]==1时），然后再把dp中所有下标为vector中的元素的值赋为1，注意不要漏了a[i]本身）
5.明确初始化--dp全部赋0

代码（数组）： 

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[100200],dp[3610];
int main(){
	int n,T;
	scanf("%d",&T);
	while(T--){
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			a[i]=a[i]%3600;
		}
		if(n>3600){
			printf("YES\n");
			continue;
		}
		for(int i=1;i<=n;i++){
			vector<ll>v;
			for(int j=0;j<=3600;j++){
				if(dp[j]) v.push_back((j+a[i])%3600);
			}
			dp[a[i]]=1;
			for(auto i:v){
				dp[i]=1;
			}
			if(dp[0]) break;
		}
		if(dp[0]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
下面还有一个代码是bitset做的，可以跑到100ms左右，比上一个代码快了10倍，原理其实和上一个代码差不多，因为方案是否存在用0/1表示，符合bitset的存储，所以开一个>3600的bitset，bitset的第i位用来存储时间%3600之后为j的方案是否存在

代码（bitset）: 

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[100200];
bitset<3610>dp;
int main(){
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			a[i]%=3600;
		}
		if(n>=3600){
			printf("YES\n");
			continue;
		}
		dp[0]=1;
		for(int i=1;i<=n;i++){
			dp|=((dp<<a[i])|(dp>>(3600-a[i])));
		}
		if(dp[3600]) printf("YES\n");
		else printf("NO\n");
		dp.reset();
	}
	return 0;
}