342

# 题目

Mr. Fib is a mathematics teacher of a primary school. In the next lesson, he is planning to teach children how to add numbers up. Before the class, he will prepare N cards with numbers. The number on the i-th card is ai. In class, each turn he will remove no more than 3 cards and let students choose any ten cards, the sum of the numbers on which is 87. After each turn the removed cards will be put back to their position. Now, he wants to know if there is at least one solution of each turn. Can you help him?

The first line of input contains an integer t(t≤5), the number of test cases. t test cases follow.
For each test case, the first line consists an integer N(N≤50).
The second line contains N non-negative integers
a1,a2,...,aN. The i-th number represents the number on the i-th card. The third line consists an integer Q(Q≤100000). Each line of the next Q lines contains three integers i,j,k, representing Mr.Fib will remove the i-th, j-th, and k-th cards in this turn. A question may degenerate while i=j, i=k or j=k.

For each turn of each case, output 'Yes' if there exists at least one solution, otherwise output 'No'.

1
12
1 2 3 4 5 6 7 8 9 42 21 22
10
1 2 3
3 4 5
2 3 2
10 10 10
10 11 11
10 1 1
1 2 10
1 11 12
1 10 10
11 11 12

No
No
No
Yes
No
Yes
No
No
Yes
Yes

# 题解

dp[i][j][k] = dp[i-1][j][k] | dp[i-1][j-1][k-num[i]]

dp[i] 表示选取 i 个数的情况下,bitset的各位能否达到

# 代码

/*/
#define debug
#include <ctime>
//*/
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 51;

int num[maxn];
bitset<90> dp[11];

int ans[maxn][maxn][maxn];
int n;

char c;
int ans = 0;
while (c = getchar(), !(c >= '0' && c <= '9'))
;
while (c >= '0' && c <= '9') {
ans *= 10;
ans += (int)c - '0';
c = getchar();
}
return ans;
}

bool getAns(int a, int b, int c) {
if (ans[a][b][c] == -1) {
for (int i = 0; i <= 10; i++)
dp[i].reset();
dp[0][0] = 1;

for (int i = 1; i <= n; ++i) {
if (i != a && i != b && i != c)
for (int t = 10; t >= 1; --t)
dp[t] |= dp[t - 1] << num[i];
}

ans[a][b][c] = dp[10][87];
}
return ans[a][b][c] == 1;
}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int START = clock();
#endif

int T = read_int();
while (T--) {
memset(ans, -1, sizeof(ans));

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

int Q = read_int();
int a[3];
for (int q = 0; q < Q; ++q) {
}