蓝桥杯 ADV-192 盾神与砝码称重

  算法提高 盾神与砝码称重  

时间限制：1.0s   内存限制：256.0MB

问题描述

　　有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。

输入格式

　　第一行为两个数，n和m。
　　第二行为n个数，表示这n个砝码的重量。
　　第三行为m个数，表示这m个物品的重量。

输出格式

　　输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。

样例输入

4 2
1 2 4 8
15 16

样例输出

YES
NO

样例输入

4 1
10 7 1 19
6

样例输出

YES

数据规模和约定

　　1<=n<=24, 1<=m<=10.

分析：判断某物是否能被称出重量，有两种方法：一是左右两端重量相等，二是左右两端的重量差可被某几个砝码所补满。由此得到判断的表达式。若某个物体被称时比未使用的所有砝码的重量之和还要重，则此物体的重量不可能被称出来。

对于某个砝码，有三种处理方式：放在左边，放在右边，不放。由此得到递归时的表达式。

代码：

#include
#include
#include
using namespace std;
int n, m;
vector w;
vector sum;
int flag = 0;
void f(int l, int r, int cnt) {if (flag == 1) {return;}if (cnt < 0) {return;}if (abs(l - r) > sum[cnt]) {return;}if (l == r || abs(l - r) == sum[cnt]) {flag = 1;return;}f(l + w[cnt], r, cnt - 1);f(l, r, cnt - 1);f(l, r + w[cnt], cnt - 1);
}
int main() {cin >> n >> m;w.resize(n);sum = w;for (int i = 0; i < n; i++) {cin >> w[i];}sort(w.begin(), w.end());sum[0] = w[0];for (int i = 1; i < n; i++) {sum[i] = sum[i - 1] + w[i];}for (int i = 0; i < m; i++) {flag = 0;int temp;cin >> temp;f(temp, 0, n - 1);printf("%s\n", flag ? "YES" : "NO");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！