0 题目来源

第十二届蓝桥杯省赛A组赛题

1 涉及到的知识点

动态规划

2 题目

3 思路

经过分析本题可以看出，放入秤上下一个砝码后，能够称出的重量数目，取决于放入上一个砝码后，能够称出的重量数目，即下一个状态取决于上一个状态，这是很明显的动态规划思想。
另外，假设现在天平可以称出重量A，则放入砝码C后，能得到的重量为A+C、|A-C|、C三种情况
因此，我们维护一个集合vec——存放天平当前能够称出的重量（不重复、不存零）。
在每次放入砝码C后，就遍历该集合vec，计算vec[i]+C、|vec[i]-c|，把计算结果以及砝码本身C加入到集合中（需要判断是否重复，若集合中已有，则不加入）
由于在遍历集合vec的过程中，是不需要遍历我们新加入的元素的（加入的砝码只与原来的重量进行运算），因此我们使用一个临时集合对新加入的元素进行存储，待遍历完成后，统一将新加入的元素加入到总集合vec中。

本思路没有采用传统的dp数组思路，之后有空会补充dp数组相关的思路。

4 代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int mp[100001];
vector<int> mainvector;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        vector<int> vec;
        for (int j = 0; j < mainvector.size(); j++)
        {
            if (!mp[temp + mainvector[j]])
            {
                mp[temp + mainvector[j]] = 1;
                vec.push_back(temp + mainvector[j]);
            }
            if (!mp[abs(temp - mainvector[j])])
            {
                mp[abs(temp - mainvector[j])] = 1;
                vec.push_back(abs(temp - mainvector[j]));
            }
        }
        for (int j = 0; j < vec.size(); j++)
        {
            if(vec[j] != 0)
                mainvector.push_back(vec[j]);
        }
        if (!mp[temp] && temp != 0)
        {
            mp[temp] = 1;
            mainvector.push_back(temp);
        }
    }
    cout << mainvector.size();
    return 0;
}