HDU 5890-Eighty seven【背包 bitset优化】

墨蓝 2023-05-31 03:10 13阅读 0赞

题意：给你n(n<50)张牌， 让后q(100000)次询问，每次会抽调三张牌，然后问你剩下的牌数能否拼成87.

思路：这题可以用背包来做，预处理出所有情况下的答案，但是会超时，这时候我们就需要bitset来优化一下了。

bitset相当于一个bool类型的数组，每次用上一次的值左移a\[i\] 位然后或上当前值，最后判断一下第87位是否为1就行了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 55;
    int a[maxn];
    bitset<90> f[12];
    bool vis[maxn][maxn][maxn];
    int n, m;
    
    bool check(int x, int y, int z)
    {
        for(int i = 0; i <= 11; ++i) f[i].reset();
        f[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)
                f[j] |= (f[j - 1] << a[i]); //相当于上一次加上a[i]
        }
        return f[10][87];
    }
    void slove()
    {   //预处理所有情况
        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))
                        vis[i][j][k] = true;
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            memset(vis, false, sizeof(vis));
            scanf("%d", &n);
            for(int i = 1; i <= n; ++i)
                scanf("%d", &a[i]);
            scanf("%d", &m);
            slove();
            int b[4];
            while(m--)
            {
                scanf("%d%d%d", &b[1], &b[2], &b[3]);
                sort(b + 1, b + 4); //优化复杂度
                if(vis[b[1]][b[2]][b[3]])
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }