HDU5890 Eighty seven

一、题目内容

【题目描述】

Fib先生是一所小学的数学老师。
在下一课中，他计划教孩子们如何加数字。
在课前，他将准备N张数字牌。第i张牌上的号码是ai。
在课堂上，每回合，他将删除不超过3张卡片，然后让学生选择任意十张卡片，其中数字的总和为87.
每次转动后，被删除的卡片将被放回原位。现在，他想知道每回合是否至少有一个解决方案。你能帮助他吗？

【输入格式】

第一行输入包含整数t（t≤5），即测试用例的数量。
对于每个测试用例，第一行包含整数N（N≤50）。
第二行包含N个非负整数a1，a2，…，aN。
第i个数字代表第i个卡上的数字。
第三行包括整数Q（Q≤100000）。
下一个Q行的每一行包含三个整数i，j，k，表示Mr.Fib将在本回合中删除第i，第j和第k个卡。当i = j，i = k或j = k时，问题可能会退化。

【输出格式】

对于每种情况的每一轮，如果存在至少一个解，则输出“是”，否则输出“否”。

【输入样例】

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

【测试网站】

HDU5890

二、题目分析

题目大意是 给出n个数和q次询问，每次删除1到3个数，问使否能从剩下的数中选10个数和为87

因为N只有50所以可以先预处理所有情况

然后用bitset <90> dp[11] 进行二维背包dp dp[i][j] 为1 代表在取i个数时能加和到 j ；

bitset 用法

三、代码示例

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <bitset>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 508 + 10;
const int maxm = 10000 + 10;
typedef pair<int,int> P;
typedef long long LL;
int n,Q;
int a[maxn];
bitset<90> dp[11];  // dp[i][j] 为1 代表在取i个数时能加和到 j
bool ans[55][55][55]; // ans[i][j][k]表示然后i,j,k后是否能组成87
bool check(int x,int y, int z)
{
  for(int i = 0; i < 11; i++)
  dp[i].reset();
  dp[0][0] = 1;
  for(int i = 1; i <= n; i++)
  {
    if(i != x && i != y && i != z)
    for(int j = 9; j >= 0; j--)
    dp[j+1] |= (dp[j] << a[i]);//二维dp + bitset优化
   }
  if(dp[10][87] == 1) return true;
  else return false;
 }

int main()
{
  int T;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    memset(ans,false,sizeof(ans));
    //预处理
    for(int i = 1; i <= n; i++)
    for(int j = i; j <= n; j++)
    for(int k = j; k <= n; k++)
  {
    if(check(i,j,k))
  {
    ans[i][j][k] = ans[i][k][j] = true;
    ans[j][i][k] = ans[j][k][i] = true;
    ans[k][i][j] = ans[k][j][i] = true;
    }
  }
  scanf("%d",&Q);
  while(Q--)
  {
    int i,j,k;
    scanf("%d%d%d",&i,&j,&k);
    if(ans[i][j][k])
    printf("Yes\n");
    else printf("No\n");
  }
 }
  return 0;
}