题解:
分成两种情况来讨论:
1.石头单独放到一边,这样就是看看石头能凑出哪些数即可。
2.另一边也可以放石头,那么那个重物就是,全为石头一边的重量-另一边石头的重量。
分好这两种情况之后就可以进行dp了。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int maxn=1e5+10;
int a[maxn];
bool dp[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin>>n){
int sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=a[i];j--){
dp[j]|=dp[j-a[i]];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=sum-a[i];j++){
dp[j]|=dp[j+a[i]];
}
}
int q;
cin>>q;
for(int i=0;i<q;i++){
int x;
cin>>x;
if(x<=sum&&dp[x]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
for(int i=0;i<=sum;i++) dp[i]=0;
}
return 0;
}

京公网安备 11010502036488号