2021年第十二届蓝桥杯决赛Python组(真题+解析+代码):最小权值

2021年第十二届蓝桥杯决赛Python组(真题+解析+代码):最小权值,第1张

2021年第十二届蓝桥杯决赛Python组(真题+解析+代码):最小权值 1 真题

 


2 解析

难度系数:⭐⭐

考察题型:动态规划

涉及知识点:DP

解题思路:

题目中的“树的权值最小可能是多少?”中的最小揭开了这道题的真正面目!DP实锤!

 DP五步:数组含义→数组赋值→遍历顺序→递推公式→打印数组

第一步:明白dp[j]的含义
 dp[i] #i:结点编号 #dp[i]:当前结点的权值
第二步:给dp数组初始化赋值
dp=[float("inf")]*2022      #创建2022个结点,置无穷大
dp[0]=0                     #第一个为空结点
第三步:弄清dp[j]遍历的顺序
for i in range(1,2022):     #遍历结点1~2021
    for j in range(i):      #遍历0~i
第四步:搞懂递推公式

谢天谢地,题目中已经给出了递推公式,直接套用就行。

 理解一下题目中的条件:结点v,有左子树L,右子树R,

如果有i个结点,那么左子树的结点为C(L)= j ,右子树的结点为C(R)= i-j-1。

dp[i]=min(dp[i],1+2*dp[j]+3*dp[i-j-1]+j*j*(i-j-1))#递推公式
第五步:打印数组
print(dp[2021])             #输出结果:2653631372

3 代码
#最小权值
dp=[float("inf")]*2022      #创建2022个结点,置无穷大
dp[0]=0                     #第一个为空结点
for i in range(1,2022):     #遍历结点1~2021
    for j in range(i):      #遍历0~i
        dp[i]=min(dp[i],1+2*dp[j]+3*dp[i-j-1]+j*j*(i-j-1))#递推公式
print(dp[2021])             #输出结果:2653631372

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710888.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存