#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 21
#define M 1000017
using namespace std;
map<int,int>mp;
int n,m,t[N],d[M],dp[M];
int main()
{
	int T;cin >> T;
	while(T--)
	{
		cin >> n >> m;
		for(int i = 0;i < n;i += 1)cin >> t[i];
		mp.clear();
		for(int i = 1;i <= m;i += 1){
			cin >> d[i];
			mp[d[i]] = 1;
		}
		memset(dp,0,sizeof(dp));
		int ed = (1<<n)-1;
		dp[0] = 1;
		for(int s = 1;s <= ed;s += 1){
			int tim = 0;
			for(int i = 0;i < n;i += 1)
				if((1<<i) & s){
					dp[s] |= dp[s-(1<<i)];
					tim += t[i];
				}
			if(mp[tim])dp[s] = 0;
		}
		if(dp[ed])cout << "YES" << endl;
		else cout << "NO" << endl;
	} 
	return 0;
}

#include <bits/stdc++.h>
//#include <inout.h>
#define int long long
#define endl "\n"
using namespace std;
map<int,int>mp;
int n,m,dp[1000005],d[1000005],a[30];
signed main() {
	int T;cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		mp.clear();
		for(int i=1;i<=m;i++)cin>>d[i],mp[d[i]]=1;
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(int s=1;s<(1<<n);s++){
			int tim=0;
			for(int i=0;i<n;i++){
				if((1<<i)&s){
					dp[s]|=dp[s-(1<<i)];
					tim+=a[i+1];
				}
			}
			if(mp[tim])dp[s]=0;
		}
		puts(dp[(1<<n)-1]?"YES":"NO");
	}
	return 0;
}

抄下面题解

抄下面题解

Solution

暴力做法：

利用$algorithm$库的$next_permutation()$函数，跑出所有全排列，并对这些排列进行检查即可

正解：

如果我们当前选择了$k$张作弊卡片，那么使用完这k张卡片后的时间$tim$为$\sum t_i$

我们将选择了哪些卡片压缩设为状态s

状态转移方程：

$dp_s |= dp_{t}(其中t为s的最大真子集，即不选某一张)$

需要注意的是：若$tim$为某个检测节点，则$dp_s$恒为0

若最终每张卡片都能被选取，则输出$YES$，否则输出$NO$