C语言网 2604：蓝桥杯2021 – 砝码称重

​

我的博客：C语言网 2604：蓝桥杯2021 – 砝码称重 – TPam的博客

题目 题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。

请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。

输入

输入的第一行包含一个整数 N。

第二行包含 N 个整数：W1, W2, W3, · · · , WN。

输出

输出一个整数代表答案。

样例输入
3
1 4 6

样例输出

10

提示

【样例说明】
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1 = 1；
2 = 6 4 (天平一边放 6，另一边放 4)；
3 = 4 1；
4 = 4；
5 = 6 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 1；
10 = 4 + 6；
11 = 1 + 4 + 6。

【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 15。

对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

思路 题目分析

任何一个砝码都可以有三种状态：放左边、放右边、不放。

如果不放，那么并不会增加或者减少结果的数量，因此可以不考虑。

接下来的思路，我不知道算不算动态规划，应该算吧。

我们把每一个能够称出来的重量都记录为一种“状态”，保存下来。

我们依次拿出砝码，将每一个砝码与之前记录的状态进行加减，得到新的状态，如果新的状态从未出现过，那么结果数量就要+1。

以题目给出的样例为例：1 4 6，初始化dp数组所有元素为0。

• 拿到1，检查状态1是否存在，不存在，状态数量++。
  

  
  

• 拿到4，检查状态4是否存在，不存在，状态数量++；然后将4与1运算，计算fabs(1-4)，得到3，发现状态不存在，状态数量++；计算1+4，得到5，发现状态不存在，状态数量++；计算状态表扫描完毕。
  

  
  

• 拿到6，重复上述过程，将6与状态1 3 4 5作运算，得到新的状态。
  

  
  

需要注意的一点是，题目中明确了，0不是合法的状态

储存结构

那么应该用什么结构来存储状态呢？由于状态是离散的、唯一的，因此不宜用顺序结构，所以可以选用STL的set；但是检查状态时如果也用set，那么就会导致超时，因为每一次查找都会耗费一定的时间，因此我们应该用一个较大的数组来标识状态是否已经得到过，这样可以在 O ( 1 ) O(1) O(1)的复杂度下完成状态查找。

用set也可以很方便的过滤掉0，最终只需要erase掉0，set的size()就是所求结果。

代码

#include 
#include 
using namespace std;

set<int> a;    // 临时
set<int> b;    // 结果
int dp[1 << 22] = { 0 };	// 随便开的一个比较大的数组

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        a = b;
        b.insert(input);
        for (set<int>::iterator it = a.begin(); it != a.end(); it++) {	// 扫描状态表
            int t1 = fabs(*it - input);
            int t2 = input + *it;
            if (dp[t1] == 0) {
                b.insert(t1);
                dp[t1] = 1;
            }
            if (dp[t2] == 0) {
                b.insert(t2);
                dp[t2] = 1;
            }
        }
    }
    b.erase(0);
    cout << b.size();
}

反思

最开始居然没有用dp数组来记忆状态，每次都去set去查，导致超时。

最开始也没设置临时set a，导致内层for循环无限执行（不断insert，一直到不了end）。

​