讨论/综合讨论/石子称重/
石子称重

小 C 想知道某件物品的重量,但是摆在他面前的只有一个天平(没有游标)和一堆石子,石子可以放左边也可以放右边。他现在知道每个石子的重量。问能不能根据上述条件,能不能测出所问的重量。


输入:
多组数据,
第一行:一个数 N,表示石子个数。(1 <= N <= 100)
第二行:N 个数,表示石子的重量。(1 <= Wi <= 100)
第三行:一个数 M,表示询问个数。(1 <= M <= 1000)
接下来 M 行:每行一个数 k(1 <= k <= 1e9),表示一个询问。

输出:
对于每组数据,输出 "YES" 或者 "NO"
样例输入

2
1 4
3
2
4
5

样例输出

NO
YES
YES
展开讨论
梦境弱者发起于 2019-12-19
最近编辑于 2019-12-20
共 2 个讨论

我理解就是指定的质量是否可以通过几个石子的质量组合碰撞出来。所以,考虑好这个组合的算法就可以了

1

使用 O(Nmax_volume)O(N * max\_volume) 的复杂度DP出每一个质量能否拼出,然后查询的时候 O(1)O(1) 回答即可。
另,max_volume2×wimax\_volume \approx 2\times \sum w_i