【蓝桥杯】第十二届蓝桥杯砝码称重（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题解）

题目【80分】

思路

知识点

代码

最新文章

热门文章

巴特西

【蓝桥杯】第十二届蓝桥杯砝码称重（Python题解）

题目 【80分】

思路

知识点

代码

最新文章

热门文章

题目【80分】