[蓝桥杯 2021 省 AB] 砝码称重

链接: P8742 [蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_{1}, W_{2}, \cdots, W_{N}$ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

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

第二行包含 $N$ 个整数: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: $1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11$ 。

$$\begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 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 \end{aligned}$$

【评测用例规模与约定】

对于 $50 \%$ 的评测用例, $1 \leq N \leq 15$ 。

对于所有评测用例, $1 \leq N \leq 100, N$ 个砝码总重不超过 $10^5$。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

题解

暴力

#include <cstdio>
#include <unordered_set>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
        
    unordered_set<int> s;
    s.insert(0);
    for (int i = 0; i < n; ++i) {
        vector<int> tmp(s.begin(), s.end()); // 枚举放于左右两边
        for (int& it : tmp) {
            s.insert(it + arr[i]);
            s.insert(abs(it - arr[i]));
        }
    }
    
    printf("%d\n", (int)s.size() - 1);
    
    return 0;
} 

C++

dp 01背包

状态转移: $dp[j]|=dp[j-a[i]],dp[j]|=dp[j+a[i]]$ (加了滚动优化)

#include <bits/stdc++.h>
using namespace std;
int a[110],n;
bitset<100010>d;
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    d.set(0);
    for(int i=1;i<=n;i++)
        cin>>a[i],d|=d<<a[i];
    for(int i=1;i<=n;i++)
        d|=d>>a[i];
    cout<<d.count()-1;
}

C++