前置知识:

背包

解题思路

题目意思其实就是一个存在性判定问题。问某一个数是否可以通过给定的数进行加减得到（每个数仅使用一次的前提下）

由于给定的石头数量很少，而且给定的石头的重量小，所以考虑对于每次询问前预处理出哪一些重量是可以被表示出来的。

不难想到这其实就是一个经典的问题：01背包，但是这个问题不能单纯用01背包来解，因为每一个数支持加上这个数或者减去这个数。

这时候我们不妨考虑做两遍 01背包，一次限定只能加上石头，一次限定只能减去石头。注意一下枚举的顺序，加石头的时候反过来从 枚举到 ，减去石头的时候就是从 枚举到 。

有人会问，两次 会不会出现有一个石头又被加上了又被减去了的情况？对于这个问题的回答我本来写了很多，但是后来我转念一想：你减去这个石头，又加上这个石头，这个重量是不会变化的啊，用 的语言解释:

你第一次枚举完是只考虑加的情况，第二次枚举的时候，假设某一个重量是通过加上这个石头得到的，那么显然这个状态原本就已经是 才能使得某一个重量通过加上这个石头达到。所以无论如何都是没有关系的。

Code

#include <bits/stdc++.h>
using namespace std;
bool dp[10005] = {1};
int A[105],n,sum = 0;
int in() {int x; scanf("%d",&x) ; return x;}
int main() {
    while(cin >> n) {
        memset(dp,0,sizeof(dp)); sum = 0;
        dp[0] = 1;
        for(int i = 1 ; i <= n ; i ++) A[i] = in() , sum += A[i];
        for(int j = 1 ; j <= n ; j ++) 
            for(int i = sum ; i >= 1 ; i --)
            if(i - A[j] >= 0) dp[i] |= dp[i - A[j]];//只考虑加上这个石头
        for(int j = 1 ; j <= n ; j ++) 
            for(int i = 1 ; i <= sum ; i ++)
            if(i + A[j] <= sum) dp[i] |= dp[i + A[j]];//只考虑减去这个石头
        int Q;
        cin >> Q;
        while(Q --) {
            int x = in();
            if(x > sum) {cout << "NO\n" ; continue;}
            if(dp[x] == 1) {cout << "YES\n" ; continue;}
            cout << "NO\n";
        }
    }
    return 0;
}