题目描述

多组输入，第一行一个，代表你有个石子，并且石子只能用一次。
第二行给出全部石子的重量。
第三行给出一个，代表询问次数。接下来有行每行一个，问重量为的物品能不能被当前有的石子测出来平衡天平。

Solution

首先观察题目范围，对于单个的最大可到，但是我们最大可以凑到的石子重量却是，根本到不了的量级。
那么我们对询问做的第一步处理就是判断是不是比出现过的全部石子之和都要大，如果大于直接输出。
对于其他情况我们再分类讨论，对于每个石子我们可以放在天平的砝码端称重，也可以放在天平的物品端和物品一起秤。
那么对于全部石子只能放在砝码端的可以使用01背包处理了，也把范围优化到了可以放下数组。
使用代表重量为的物品可以求到它的重量。
一遍正向的01背包把全部石子只能放在砝码端可以求到的重量记录下来，接下来再去反向跑一遍01背包，把当前枚举的石子放在物品端，看看有那些情况也符合的，一并记录即可。注意方向不一致带来的01背包的第二维起点和终点的不同。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll n, m;
ll dp[N], a[N];
void solve() {
    int sum = 0;
    rep(i, 1, n) {
        a[i] = read();
        sum += a[i];
    }
    ms(dp, 0);
    dp[0] = 1;
    rep(i, 1, n) { // 01背包放在砝码堆
        for (int j = sum; j >= a[i]; --j)
            dp[j] |= dp[j - a[i]];
    }
    rep(i, 1, n) { // 01背包放在物品堆
        for (int j = 1; j <= sum - a[i]; ++j)
            dp[j] |= dp[j + a[i]];
    }
    m = read();
    rep(i, 1, m) {
        int k = read();
        if (k > sum)    puts("NO");
        else if (dp[k])    puts("YES");
        else puts("NO");
    }
}

int main() {
    //int T = read();    while (T--)
    while (cin >> n)    solve();
    return 0;
}