?題干：

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?NN?cards with numbers. The number on the?ii-th card is?aiai. In class, each turn he will remove no more than?33?cards and let students choose any ten cards, the sum of the numbers on which is?8787. 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?

Input

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

Output

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

Sample Input

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

Sample Output

No No No Yes No Yes No No Yes Yes

題目大意：

50個數，10W個詢問，每次問刪掉第i,j,k個數后，是否存在一種選10個數和為87的方案，只需要輸出 ’Yes’ 或者 ’No’

解題報告：

? ?直接可行性背包，然后bitset優化一下就可以了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #include<bitset> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; bitset<111> bs[111]; int a[MAX],n; bool dp[111][111][111]; bool ok(int x,int y,int z) {for(int i = 1; i<=n; i++) bs[i].reset();bs[0][0]=1;for(int i = 1; i<=n; i++) {if(i == x || i == y || i == z) continue;for(int j = 10; j>=1; j--) {bs[j] |= (bs[j-1] << a[i]);}}return bs[10][87]; } int main() {int t;cin>>t;while(t--) {scanf("%d",&n);memset(dp,0,sizeof dp);for(int i = 1; i<=n; i++) scanf("%d",a+i);for(int i = 1; i<=n; i++) {for(int j = i; j<=n; j++) {for(int k = j; k<=n; k++) {dp[i][j][k]=0;if(ok(i,j,k)) dp[i][j][k] = 1;}}}int q,x[4];scanf("%d",&q);while(q--) {for(int i = 1; i<=3; i++) scanf("%d",x+i);sort(x+1,x+4);if(dp[x[1]][x[2]][x[3]] == 1) puts("Yes");else puts("No");}}return 0 ; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【HDU - 5890】Eighty seven（bitset优化背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。