提供一种新做法,理论复杂度更快,我们用bitset加速维护
发现一共只有三种可能,放左边放右边和不放
我们初始设定一个sum以防负数,然后左右移位就可以了
代码:
#include<bits/stdc++.h> using namespace std; #define LL long long #define DB double #define M 20200 int n,a[M],Q; bitset<M>B,tmp; int main(){ while(scanf("%d",&n)!=EOF){ int all=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]),all+=a[i]; B.reset(),B[all]=true; for(int i=1;i<=n;i++) tmp=B,B|=(B<<a[i]),B|=(B>>a[i]); scanf("%d",&Q); while(Q--){ int x; scanf("%d",&x); if(x>all) puts("NO"); else puts((B[all+x]||B[all-x])?"YES":"NO"); } }return 0; }