Weight Measure

Problem Statement

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

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

Input

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

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

Output

输出一个整数代表答案。

Sample Input

Sample Output

1

10

Explanation of example

能称出的 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} $$

Constraints

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

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

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

Solving

01背包求方案数的模板题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


void solve()
{
    int n;
    cin >> n;
    int arr[n+1];
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    bool dp[sum+1];
    memset(dp,false,sizeof dp);
    dp[0] = true;
    dp[sum] = true;
    //先只放到一边
    for(int i=1;i<=n;i++)
    {
        for(int j=sum;j>=arr[i];j--)
        {
            if(dp[j-arr[i]])
            dp[j] = true;
        }
    }
    //将每一个移向另一边
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum-arr[i];j++)
        {
            if(dp[j+arr[i]])
            dp[j] = true;
        }
    }
    int cnt = 0;
    for(int i=1;i<=sum;i++)
    if(dp[i]) cnt++;
    cout << cnt;
}

使用Bitset空间优化后的版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


const int N = 1e7+10;
const int M = 0; 
bitset<N> dp;
void solve()
{
    int n;
    cin >> n;
    int val[n+1];
    for(int i=1;i<=n;i++) cin >> val[i];
    dp[0] = 1;
    for(int i=1;i<=n;i++)
    {
        dp |= dp << val[i];
        //表示将dp向左边移动val[i]位后与原dp进行与或操作
    }
    for(int i=1;i<=n;i++)
    {	
        //表示将dp向右边移动val[i]位后与原dp进行与或操作
        dp |= dp >> val[i];
    }
    cout << dp.count()-1;
}