【蓝桥杯】第十二届蓝桥杯砝码称重(Python题解)
2021/12/25 17:07:51
本文主要是介绍【蓝桥杯】第十二届蓝桥杯砝码称重(Python题解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
@
目录- 题目 【80分】
- 思路
- 知识点
- 代码
题目 【80分】
你有一架天平和N个砝码,这N个砝码重量依次是W1,W2,……,WN请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
【样例输入】
3
1 4 6
【样例输出】
10
思路
这是一道动态规划题
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
知识点
将dp初始化为0,二维数组
对于第一个加入的dp[i][array[0]]=1标记为能称出的重量
最终dp:
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第一次加入1,所以在dp[0,1] 这里标记为1
[0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
第二次加入4,所以在dp[1][4] 这里标记为1,之前的状态为dp[0][1]也是为1,之后在加入4之后;4+1=5,所以dp[1][5]标记为1,abs(1-4)==3,所以dp[1][3]也标记为1;
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
同理:
所以最后求解个数的时候只需要将求解dp数组最后一行有多少个1,也就能得出答案
思路是没问题,不过这道题最后两个测试样例超时了只有80分
代码
n = int(input()) array = list(map(int, input().split())) sum = sum(array) a_len = len(array) ans = 0 dp = [[0 for i in range(sum+1)] for j in range(a_len)] dp[0][array[0]]=1 # no1 for i in range(1,a_len): for j in range(1,sum+1): dp[i][j]=dp[i-1][j] # copy 对于当前的复制前一个的重量 dp[i][array[i]]=1 # 当前状态是可称的 for j in range(1, sum+1): # 最大重量为所有砝码重量总和 if(dp[i-1][j]): #pre=1 上一个状态的重量 dp[i][j+array[i]] = 1 # 上一状态的重量在加上当前重量 dp[i][abs(j-array[i])]=1 # 上一个状态的重量减去当前状态的重量 for i in range(1,sum+1): if(dp[n-1][i]): ans += 1 print(ans)
这篇关于【蓝桥杯】第十二届蓝桥杯砝码称重(Python题解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-20Python编程入门指南
- 2024-12-20Python编程基础与进阶
- 2024-12-19Python基础编程教程
- 2024-12-19python 文件的后缀名是什么 怎么运行一个python文件?-icode9专业技术文章分享
- 2024-12-19使用python 把docx转为pdf文件有哪些方法?-icode9专业技术文章分享
- 2024-12-19python怎么更换换pip的源镜像?-icode9专业技术文章分享
- 2024-12-19Python资料:新手入门的全面指南
- 2024-12-19Python股票自动化交易实战入门教程
- 2024-12-19Python股票自动化交易入门教程
- 2024-12-18Python量化入门教程:轻松掌握量化交易基础知识