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

1 真题


2 解析

难度系数:⭐⭐

考察题型:动态规划

涉及知识点:DP

解题思路:

题目中的“树的权值最小可能是多少?”中的最小揭开了这道题的真正面目q(≧▽≦q)

DP实锤!下面请欣赏:如何用5行代码秒杀这道题?

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

第一步:明白dp[j]的含义

 dp[i] #i:结点编号 #dp[i]:当前结点的权值

第二步:给dp数组初始化赋值

dp=[0]+[float("inf")]*2021 #空结点+2021个无穷大结点

第三步:弄清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=[0]+[float("inf")]*2021  #空结点+2021个无穷大结点
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

DP模板

#模板
dp=[]*(n+1)                             #1.dp数组初始化      
dp[x]=[]                                #2.特殊值赋值
for i in range():                       #3.循环遍历
  for j in range():
    dp[j]=min(dp[j],dp[i]+abc(i,j))     #4.递推公式
print(dp[n])                            #5.打印数组

      我写的是关于蓝桥杯的系列题解,感谢关注我的朋友们,我会持续输出高质量文章           蓝桥杯python组十二届决赛真题+解析+代码(通俗易懂版)_编程有了思路-CSDN博客小蓝家的网络带宽是 200 Mbps,请问,使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 MB 的内容。如果一个正整数只有 1 和它本身两个约数,则称为一个质数(又称素数)。如果一个日期中年月日的各位数字之和是完全平方数,则称为一个完全日期。https://blog.csdn.net/m0_55148406/article/details/122790101

你可能感兴趣的