砝码称重

第十二届蓝桥杯省赛真题

题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W₁, W₂, ···, W_N。

请你计算一共可以称出多少种不同的正整数重量**（不含0）**。

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

输入格式

• 第一行包含一个整数 N
• 第二行包含 N 个整数：W₁, W₂, ···, W_N

输出格式

输出一个整数代表答案。

数据范围

• 对于 50% 的评测用例，1 ≤ N ≤ 15
• 对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 10⁵

输入样例

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

补充说明：

1. 题目重点在于砝码可以放在天平两侧，因此需要考虑加减两种情况
2. 数据范围强调N≤100且总重≤10⁵，暗示需要使用动态规划等高效算法
3. 样例解释详细展示了如何通过砝码组合得到不同重量