第十二届蓝桥杯试题G:砝码称重 Python题解

artrajz

March 7, 2022

1426 views

No comments

1291 words

题解

## 前言

> 作为一只有自知之明的菜鸟，为了对抗自己的懒癌，决定以每天至少写一道题并发布来督促自己。。（老头环实在是太好玩了）

## 题目

![](https://s1.ax1x.com/2022/03/07/byCcEn.png)
![](https://s1.ax1x.com/2022/03/07/byCX8K.png)

## 思路

运用dp思想，通过前面的组合推出后面的组合，并添加进入dp中，以供下一轮组合。

dp使用set类型，可以去重，避免重复组合影响速度。

比如：

```
3
1 4 6
```

dp先加入一个0

在第一轮组合中，加入0**+1**,0**-1**,此时dp={0,**1，-1**}

在第二轮组合中，加入0**+4**,0**-4**,1**+4**,1**-4**,-1**+4**,-1**-4**,此时dp={0,1,-1,**4,-4,5,-3,3,-5**}

在第三轮组合中，加入0**+6**,0**-6**,1**+6**,1**-6**,-1**+6**,-1**-6**,4**+6**,4**-6**,-4**+6**,-4**-6**,5**+6**,5**-6**,-3**+6**,-3**-6**,3**+6**,-3**-6**,-5**+6**,-5**-6**,此时dp={0,1,-1,4,-4,5,-3,6,-6,7,-5,**-7,10,-2,2,-10,11,3,-9,9,-11**}

这样就可以把所有可能的组合计算出来

根据常识，砝码称重能够称的重量一定大于0，所以最后再计算dp中大于0的个数。

先加入0的作用是可以在循环中加入当前数本身的状态（1,-1,4,-4,6,-6），不这么做也可以自行另外添加。

自认为这种解法还是比较简单的，但是可惜达不到满分。。

PS：目前我在网上搜到的Python题解只有80分，而且解题思路和大佬的c++/java版本一样，但是Python套用过来就只有80分，看来Python在速度上确实略逊一筹。。

## 题解

```python
n = int(input())
num = list(map(int,input().split()))
dp = set()
dp.add(0)
for i in range(0,n):
    for j in dp.copy():
        dp.add(j+num[i])
        dp.add(j-num[i])

##    print(dp)

count = 0
for i in dp:
    if i > 0:
        count+=1
print(count)
```

![评测结果](https://s1.ax1x.com/2022/03/07/by9dOJ.md.png "评测结果")

Last modification：March 12, 2022