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

1728 阅读 6 评论 4 点赞

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

5 人评分

本文分类：题解列表
浏览次数：1728 次浏览
发布日期：2018-06-18 22:38:26
本文链接：https://blog.dotcpp.com/a/8440

上一篇 > Tom数（C++代码）
下一篇 > C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 6 条评论

昵称和用户名有区别吗 3年前回复TA

膜拜大佬

Patient 4年前回复TA

这方法有点强

HzuWHF 4年前回复TA

@列公子 dp 值为 1 表示可以组合出来，用滚动数组由 dp【0】【】推出 dp【1】【】，dp【】【 50000 】是零点，相当于什么都没放，dp【】【 < 50000 】可以理解为砝码放在左边，反过来就是右边。

列公子 4年前回复TA

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

小于哥的鱼干 6年前回复TA

真的很佩服！

tiffnic 6年前回复TA

好厉害！明年ACM带我！

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 6 条评论

发表评论 取消回复

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

评论列表共有 6 条评论

发表评论取消回复