HzuWHF

```cpp
DFS每种情况：每个砝码 3 种状态，假设左边为正，右边为负，遍历 3 种状态即可。
OPT(num - 1, sum + datas[num]); 第 num 个砝码放左边。
OPT(num - 1, sum);              这个砝码不放。
OPT(num - 1, sum - datas[num]); 第 num 个砝码放右边。
```
```cpp
复杂度 O(3^N)，理论上大概只能跑到 N = 17，这边数据应该没有太大，所以能通过本题。
```

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
 
int value, datas[233]; bool poi;
 
void OPT(int num, int sum) {
    if (sum == value) { poi = true; return;  }
    if (num < 0) return;
    OPT(num - 1, sum + datas[num]);
    OPT(num - 1, sum);
    OPT(num - 1, sum - datas[num]);
}
 
int main() {
    int num, quan;  cin >> num >> quan;
    for (int i = 0; i < num; i++) cin >> datas[i]; 
    while (quan--) {
        poi = false;
        cin >> value;
        OPT(num - 1, 0);
        if (poi) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
```

```cpp
本题正解应该是Dp，复杂度为 O(Ｎ * w)，w为所询问的重量最大值。
```

```cpp
constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
    #include <bits/stdc++.h>
#endif
typedef long long LL;
using namespace std;
namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) != 'c' && o != 'd'); return o;
    }
}
using namespace IO;
int Dp[2][100000];
int main() {
    int N = read(), M = read();
    Dp[0][50000] = 1;
    for (int pos = 1, e; pos <= N; pos++) {
        e = read();
        for (int w = 0; w < 100000; w++)
            Dp[1][w] = Dp[0][w];
        for (int w = 0; w < 100000; w++)
            if (Dp[0][w]) {
                Dp[1][w + e] = 1;
                if (w - e > 0) Dp[1][w - e] = 1;
            }
        swap(Dp[0], Dp[1]);
    }
    for (int pos = 1, e; pos <= M; pos++)
        e = read(), puts((Dp[0][50000 + e] || Dp[0][50000 - e]) ? "YES" : "NO");
}
```

0.0分

6 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

昵称和用户名有区别吗

膜拜大佬

2021-01-30 11:33:38

Patient

这方法有点强

2020-12-16 16:39:12

列公子

能说一下 dp 是怎么定义的吗？

2020-02-23 16:27:00

小于哥的鱼干

真的很佩服！

2018-09-27 16:06:09

tiffnic

好厉害！明年ACM带我！

2018-07-02 20:20:46

HzuWHF

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

剪刀石头布（Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯算法提高VIP-盾神与砝码称重（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

点我有惊喜！你懂得！

C语言训练-计算1~N之间所有奇数之和（C语言代码）

简单的a+b （C语言代码）

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

核桃的数量（C语言代码）

HzuWHF

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

剪刀石头布 （Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯算法提高VIP-盾神与砝码称重 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

点我有惊喜！你懂得！

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

简单的a+b （C语言代码）

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

核桃的数量 （C语言代码）

母牛的故事（C语言代码）

剪刀石头布（Java代码）

蓝桥杯算法提高VIP-盾神与砝码称重（C++代码）

　　评论区

C语言训练-计算1~N之间所有奇数之和（C语言代码）

汽水瓶（C语言代码）

【计算直线的交点数】（C语言代码）

核桃的数量（C语言代码）