作物杂交【第十一届】【省赛】【B组】Python 【递归+记忆化搜索+倒序dfs+dp】

题目描述
作物杂交是作物栽培中重要的一步。

已知有 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 天。

分析：

1 首先仔细读题！不要着急
2 在写代码时候最好在旁边写上数据样例，方便编程！
3 在编代码时多打印中间结果发现规律！尤其是递归！！

思路：
如果要获得6号作物，我们需要首先获得4 5 号作物以及其杂交最短时间，而获得4 5 号作物这又是一个递归 求啥搜啥！所以倒序搜

考虑dfs，去从目标倒过来直到搜索已知作物
加以记忆化搜索防止超时！搜啥设啥 ，肯定设获取第i种作物的最短时间

min_time[i]记录获取到第 i种作物的最短时间，默认为无穷大float(“inf”)(有点dp的意思，但又不全是。

。

。

)，如果min_time已经搜过直接返回，没有搜过的话=min（本身，新杂交方案）

因为要找最小的，肯定要与自己比较取min

这里还要注意的一个坑是：一种作物的杂交方案不一定只有一种，不要被样例骗了！

我们在dfs中就是遍历i的所有杂交方案进行递归的。

这就涉及到了i杂交方案怎么存储，这里用mix【i】表示i的杂交方案
用二维的，每个mix【i】是一个列表，存储多种杂交方案

如mix=[[], [], [], [[1, 2, 5]], [[1, 3, 5]], [[2, 3, 4]], [[4, 5, 6]]]
mix[i]:杂交方案 i:目标作物

记忆化搜索中最核心的代码

 for j in range( len(mix[i])):#遍历i作物的所有杂交方案j=0 1 2
    min_time[i]=min(min_time[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1]))+mix[i][j][2])
    #min_time[i]=min（本身已经最小不更新，max(获取a作物的最短时间，获取b作物的最短时间)+杂交ab作物的时间)

一定要理解递归的思想，不要去深究
必要时候可以手推一下，去找规律

			#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 

代码

n,m,k,t=map(int,input().split())
cost=list(map(int,input().split()))
have = list(map(int,input().split()))

mix=[[] for i in range(n+1)]#杂交列表初始化为空,每个植物都有对应mix[i]代表第i种作为
for i in range(k):
  a,b,c=map(int,input().split())#杂交方案 1+2→3 #1+3→4 #2+3→5 #4+5→6
  max_time = max(cost[a - 1], cost[b - 1])
  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]]]
  # [[[],[],[]]]这种格式是因为一种作物可能存在多种杂交方案?对！例如第三种作物可以有两种杂交方式[[1, 2, 5]，[5,1,5]]
  # mix[i]:杂交方案 i:目标作物

min_time=[float("inf") for i in range(n+1)]#每种作物培养时间初始化为无穷大，因为要找最小的
for i in have:
  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])):#i作物的所有杂交方案j=0 1 2
    min_time[i]=min(min_time[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1]))+mix[i][j][2])
    #min_time[i]=min（本身已经最小不更新，max(获取a作物的最短时间，获取b作物的最短时间)+杂交ab作物的时间)
			#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(have)
#print(mix)
dfs(t)
print(min_time[t])