备战蓝桥杯|2020年第十一届蓝桥杯省赛Python组（真题+解析+代码）（作物杂交）动态规划|蓝桥杯|python|职场和

1 真题

题目描述
作物杂交是作物栽培中重要的一步。已知有 N种作物 (编号 1 至 N )，第 i 种作物从播种到成熟的时间为 Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。
初始时，拥有其中 M种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。
如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：
第 1 天到第 7 天 (作物 B 的时间)，A × B → C。
第 8 天到第 12 天 (作物 A 的时间)，A × C → D。
花费 12 天得到作物 D 的种子。

输入描述
输入的第 1 行包含 4 个整数 N, M, K, T，N表示作物种类总数 (编号 1 至 N)，M表示初始拥有的作物种子类型数量，K表示可以杂交的方案数，T表示目标种子的编号。
第 2 行包含 N 个整数，其中第 i个整数表示第 i 种作物的种植时间 Ti(1<=Ti<=100)
第 3 行包含 M 个整数，分别表示已拥有的种子类型 Kj (1 <= Kj ≤ M)，Kj 两两不同。
第 4 至 K+ 3 行，每行包含 3 个整数 A, B,C，表示第 A类作物和第 B 类作物杂交可以获得第 C 类作物的种子。
其中，1 <= N<= 2000, 2<= M <= N, 1 <= K <=10^5, 1 <= T <= N
保证目标种子一定可以通过杂交得到。

输出描述
输出一个整数，表示得到目标种子的最短杂交时间。

样例输入

6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6

样例输出

16

样例说明
第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。
第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。
第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。
第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。
总共花费 16 天。

2 解析难度系数：???
考察题型：查找动态规划
涉及知识点：DFS DP

思路分析：
第一步：审题。我足足看了10分钟这个题目，才晓得作物杂交具体在干啥。
第二步：输入。输入题目中的各种条件，最好旁边写上样例输入，更方便理解，不被绕晕。
第三步：搜索。从目标作物递推回已知作物，写个dfs函数。
具体DFS思路参考评论区小郑大佬的详细解释！? ω ?

3 代码详细注释版

#作物杂交-dfs n,m,k,t=map(int,input().split())#n:种子编号-6类 m:初始种子数量-2个 k:杂交方案-4种 t:目标种子编号-6号 T=list(map(int,input().split()))#种植时间 T=[5,3,4,6,4,9] K=list(map(int,input().split()))#已拥有的种子类型 M=[1,2]mix=[[] for i in range(n+1)]#杂交列表初始化为空 for i in range(k):#输入4种杂交方案 a,b,c=map(int,input().split())#杂交方案 1+2→3 #1+3→4 #2+3→5 #4+5→6 max_time=max(T[a-1],T[b-1])#杂交最长时间 5 5 4 6 ls=[a,b,max_time]#ls=[种子a,种子b,杂交最长时间] [1,2,5] [1,3,5] [2,3,4] [4,5,6] mix[c].append(ls)#mix=[[], [], [], [[1, 2, 5]], [[1, 3, 5]], [[2, 3, 4]], [[4, 5, 6]]] #[[[],[],[]]]这种格式是因为一种作物可能存在多种杂交方案 #mix[i]:杂交方案 i:目标作物min_time=[float("inf") for i in range(n+1)]#作物培养时间初始化为无穷大 for i in K:#初始化已有种子的培养时间为0 min_time[i]=0 #min_time=[0,0,0,inf,inf,inf···] def dfs(i):#获取目标作物所需时间 if min_time[i]!=float("inf"):#计算过的作物直接返回 return min_time[i] for j in range(len(mix[i])):#遍历一种作物的所有杂交方案 min_time[i]=min(min_time[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1]))+mix[i][j][2]) #min_time[6]=min(inf,max(dfs(4),dfs(5))+6h)=16h #min_time[5]=min(inf,max(dfs(2),dfs(3))+4h)=9h #min_time[4]=min(inf,max(dfs(1),dfs(3))+5h)=10h #min_time[3]=min(inf,max(dfs(1),dfs(2))+5h)=5h #dfs(1)=0 #dfs(2)=0 return min_time[i]print(dfs(t))#dfs(6)

精简考试版

#作物杂交 n,m,k,t=map(int,input().split()) T=list(map(int,input().split())) K=list(map(int,input().split())) mix=[[] for i in range(n+1)] for i in range(k): a,b,c=map(int,input().split()) max_time=max(T[a-1],T[b-1]) ls=[a,b,max_time] mix[c].append(ls) dp=[float("inf") for i in range(n+1)] for i in K: dp[i]=0 def dfs(i): if dp[i]!=float("inf"): return dp[i] for j in range(len(mix[i])): dp[i]=min(dp[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1]))+mix[i][j][2]) return dp[i] print(dfs(t))

【备战蓝桥杯|2020年第十一届蓝桥杯省赛Python组（真题+解析+代码）（作物杂交）】我写的是关于蓝桥杯的系列题解，感谢关注我的朋友们，我会持续输出高质量文章