HzuWHF

用户名：I7I08I9047

访问量：83350

签　名：

我RUN了

等　　级
排　　名	19
经　　验	21266
参赛次数	13
文章发表	127
年　　龄	3
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1588-数字游戏-题解（C++代码）
浏览：269

你可能喜欢

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

　　作者: HzuWHF　　　　发表时间：2018-06-18 22:38:26 浏览：1703　|　评论：5　

原题链接：蓝桥杯算法提高VIP-盾神与砝码称重

```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分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

昵称和用户名有区别吗

膜拜大佬

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语言程序设计教程（第三版）课后习题6.1 （C语言代码）

兰顿蚂蚁（C语言代码）

小九九（C语言代码）

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

C语言训练-数字母（C语言代码）

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

评论区

精彩推荐

C语言训练-计算一个整数N的阶乘（C语言代码）

A+B for Input-Output Practice (V) （C++代码）

蛇行矩阵（C语言代码）

【简单计算】（C语言代码）

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

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

字符串输入输出函数（C语言代码）

C二级辅导-等差数列（C语言代码）

老王赛马（C++代码）

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

HzuWHF

TA的其他文章

你可能喜欢

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

兰顿蚂蚁 （C语言代码）

小九九 （C语言代码）

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

C语言训练-数字母 （C语言代码）

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

评论区

精彩推荐

C语言训练-计算一个整数N的阶乘 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

蛇行矩阵 （C语言代码）

【简单计算】 （C语言代码）

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

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

字符串输入输出函数 （C语言代码）

C二级辅导-等差数列 （C语言代码）

老王赛马 （C++代码）

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

兰顿蚂蚁（C语言代码）

小九九（C语言代码）

C语言训练-数字母（C语言代码）

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

　　评论区

C语言训练-计算一个整数N的阶乘（C语言代码）

蛇行矩阵（C语言代码）

【简单计算】（C语言代码）

字符串输入输出函数（C语言代码）

C二级辅导-等差数列（C语言代码）

老王赛马（C++代码）