蓝桥杯备赛 [day11]3月26日｜python｜作物杂交——＞查找DFS和amp;动态规划DP

目录

1.题目描述

2.输入描述

3.输出描述

4.输入输出样例

4.1示例

4.1.1输入

4.1.2输出

4.2样例说明

5.程序设计

5.1解题思路

5.2程序代码

6.总结

---

1.题目描述

作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号1 至 N)，第 i 种作物从播种到成熟的时间为 Ti 。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。

初始时，拥有其中 M 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 A: 5 天、B: 7 天、C: 3 天、D: 8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：

第 1 天到第 7 天 (作物 B 的时间)，A × B → C。

第 8 天到第（7 5） 12 天 (作物 A 的时间)，A × C → D。

花费 12 天得到作物 D 的种子。

2.输入描述

输入的第 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， 保证目标种子一定可以通过杂交得到。

3.输出描述

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

4.输入输出样例

4.1示例

4.1.1输入

1.  
   第一行
2.  
   6#作物种类总数
3.  
   2#初始拥有的作物种子类型数量
4.  
   4#可以杂交的方案数
5.  
   6#目标种子的编号
6.  
    
7.  
   第二行
8.  
   5 3 4 6 4 9
9.  
   第三行 已经拥有的种子类型
10.  
    1 2
11.  
     
12.  
    第四行 及以后
13.  
    #1*2——>3 1*3——>4 2*3——>5 4*5——>6
14.  
    1 2 3
15.  
    1 3 4
16.  
    2 3 5
17.  
    4 5 6

4.1.2输出

16

4.2样例说明

第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。

第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。

第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。

第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。

总共花费 16 天。

5.程序设计

5.1解题思路

首先注意输入要求，第一行要包括四个数据，我们可以用map（）函数来实现input（）批量输入；

第二行，第三行的输入要为以后找最短天数提供数据，我们将其用列表的方式存储，便于后续使用；

接下来定义搜索函数dfs（），其中的参数T便是我们要求的目标作物，当目标作物在已知的have中时，此时需要的时间就是0；

当其不在其中时，我们就在杂交方式ways（第四行及以后）中找到目标作物T，此时的ways中的元素中的小列表中的第三个元素便是我们的T，顺势我们将此小列表中得到T的那两个元素也在times中找到，看看他们所需要的时间，取他们其中的最大值tmp = max(times[i[0]-1], times[i[1]]-1)；

紧接着采用递归的方式看看其余的这两个元素是否在已知的have中存在，若存在则时间是0，不存在则时间采用同种方式继续求得，此时的time便为min_t =max(dfs(i[0]), dfs(i[1])) tmp；

如果在have或者ways中没有我们所要的目标元素，那需要的时间就还是无限的，因此在开始时我们要把时间time定义为无限大，当只有在have或者ways中找到我们要得到的元素时，我们在能进一步得到一个具体的时间min_t ，此时让time = min_t，最后函数结束return 我们的time。

5.2程序代码

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

1.  
   import math
2.  
   #作物杂交
3.  
   n,m,k,t=map(int,input().split())
4.  
   T=list(map(int,input().split()))
5.  
   K=list(map(int,input().split()))
6.  
   mix=[[] for i in range(n 1)]
7.  
   for i in range(k):
8.  
   a,b,c=map(int,input().split())
9.  
   max_time=max(T[a-1],T[b-1])
10.  
    ls=[a,b,max_time]
11.  
    mix[c].append(ls)
12.  
    dp=[float("inf") for i in range(n 1)]
13.  
    for i in K:
14.  
    dp[i]=0
15.  
    def dfs(i):
16.  
    if dp[i]!=float("inf"):
17.  
    return dp[i]
18.  
    for j in range(len(mix[i])):
19.  
    dp[i]=min(dp[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1])) mix[i][j][2])
20.  
    return dp[i]
21.  
    print(dfs(t))

1.  
   import os
2.  
   import sys
3.  
    
4.  
   # 请在此输入您的代码
5.  
    
6.  
   #作物杂交
7.  
   n,m,k,t=map(int,input().split())
8.  
   T=list(map(int,input().split()))
9.  
   K=list(map(int,input().split()))
10.  
    mix=[[] for i in range(n 1)]
11.  
    for i in range(k):
12.  
    a,b,c=map(int,input().split())
13.  
    max_time=max(T[a-1],T[b-1])
14.  
    ls=[a,b,max_time]
15.  
    mix[c].append(ls)
16.  
    dp=[float("inf") for i in range(n 1)]
17.  
    for i in K:
18.  
    dp[i]=0
19.  
    def dfs(i):
20.  
    if dp[i]!=float("inf"):
21.  
    return dp[i]
22.  
    for j in range(len(mix[i])):
23.  
    dp[i]=min(dp[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1])) mix[i][j][2])
24.  
    return dp[i]
25.  
    print(dfs(t))

报错

import math

N, M, K, T = map(int, input().split()) #四个整数

times = list(map(int, input().split())) #作物的种植时间

have = list(map(int, input().split())) #已经拥有的种子类型

ways = [] #杂交方式

for i in range(K):

ways.append(list(map(int, input().split())))

# 定义dfs函数搜索情况，参数T是目标种子

def dfs(T):

# 出口

if T in have:

return 0

# 寻找目标种子

time = math.inf

for i in ways:

if i[2] == T:

tmp = max(times[i[0]-1], times[i[1]]-1)

min_t = max(dfs(i[0]), dfs(i[1])) tmp

time = min_t

return time

print(dfs(T))

6.总结

        用Mix[i]数组存储生成i的所有方案，方案由种子1和种子2及种植时间构成，Mix形成了三层列表；初始化未获得的种子时间min_time[i]为float('inf') 创建一个函数，返回获得目标种子的最短时间min_time[i] ；在调用函数的过程中，如果min_time[i]不等于无穷，说明获得i种子的时间已获得最优解，直接返回。否则DFS，遍历种子i的所有方案，不断更新最短时间(与上一轮进行比较) 而本轮的最短时间由三个要素决定：min_time[i]=max（获取原材料1的最短时间，获取原材料2的最短时间) max(原材料1的种植时间，原材料2的种植时间) 。

点赞 收藏 支持一下吧～ 

于 2023-03-27 21:35:32 首次发布

这篇好文章是转载于：学新通技术网