题目描述
作物杂交是作物栽培中重要的一步。已知有 NN 种作物 (编号 11 至 NN ),第 ii 种作物从播种到成熟的时间为 T_iTi。作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天,作物 B 种植时间为 7 天,则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物,新产生的作物仍然属于 NN 种作物中的一种。
初始时,拥有其中 MM 种作物的种子 (数量无限,可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子,最少需要多少天能够得到。
如存在 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, TN,M,K,T,NN 表示作物种类总数 (编号 11 至 NN),MM 表示初始拥有的作物种子类型数量,KK 表示可以杂交的方案数,TT 表示目标种子的编号。
第 2 行包含 NN 个整数,其中第 ii 个整数表示第 ii 种作物的种植时间 T_i\ (1 \leq T_i \leq 100)Ti (1≤Ti≤100)。
第 3 行包含 MM 个整数,分别表示已拥有的种子类型 K_j\ (1 \leq K_j \leq M)Kj (1≤Kj≤M),K_jKj 两两不同。
第 4 至 KK + 3 行,每行包含 3 个整数 A, B,CA,B,C,表示第 AA 类作物和第 BB 类作物杂交可以获得第 CC 类作物的种子。
其中,1 \leq N \leq 2000, 2 \leq M \leq N, 1 \leq K \leq 10^5, 1 \leq T \leq N1≤N≤2000,2≤M≤N,1≤K≤105,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
解题思路:
首先要注意一点:产生某种种子的杂交方案可能不止一种,我一开始就是没考虑这点,所以测试数据一个都没通过。
以题目给出的样例来解释:我们要得到6号种子,就要先得到4号种子和5号种子;所以问题就分解为求4号种子和5号种子的最短杂交时间;然后,我们要得到4号种子,就要先得到1号种子和3号种子,这里1号种子最初就已经有了,所以我们记1号种子的最短杂交时间为0;要得到3号种子,就要先得到1号种子和2号种子,而这两种种子的最短杂交时间已经有了(这里都是0),所以计算(计算时要用到种植时间)得出3号种子的最短杂交时间;这时候1号种子和3号种子的最短杂交时间都已经有了,所以我们可以计算得出4号种子的最短杂交时间;对5号种子也是如此,最后可以计算得到6号种子的最短杂交时间。
这里要用到递归和回溯的思想。另外,对于某种种子,若求出了它的最短杂交时间,我们就将其保存下来,这样可以避免后续多余的计算,大幅节省时间。
再强调一次:上述样例中,得到3、4、5、6号种子的杂交方案均只有一种,但实际上,可以有很多种,解题时要考虑每种方案,并取时间最短的那个。
程序代码:文章来源:https://www.toymoban.com/news/detail-409334.html
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
const int maxn = 2010;
int N, M, K, T;
vector<int>times(maxn); //保存种子的种植时间
vector<int>early(maxn, -1); //保存种子的最短杂交时间(初始化为-1)
vector<int>part[maxn]; //保存产生种子i的杂交方案(很可能大于一种)
int DFS(int target);
int main()
{
cin >> N >> M >> K >> T;
for (int i = 1; i <= N; i++) {
cin >> times[i];
}
int m;
for (int i = 1; i <= M; i++) {
cin >> m;
early[m] = 0; //对于原本就有的种子,最短杂交时间设为0
}
int a1, a2, a3;
for (int i = 1; i <= K; i++) {
cin >> a1 >> a2 >> a3;
//每两个数为一组杂交方案
part[a3].push_back(a1);
part[a3].push_back(a2);
}
int ans = DFS(T);
cout << ans << endl;
return 0;
}
int DFS(int target)
{
int a, b;
early[target] = 1e9;
//杂交方案可能不止一种,要求出所有方案,再选择最优的
for (int i = 0; i + 1 < part[target].size(); i += 2) {
//a,b两个数构成一个杂交方案
a = part[target][i];
b = part[target][i + 1];
if (early[a] == -1) {
//求a的最短杂交时间
early[a] = DFS(a);
}
if (early[b] == -1) {
//求b的最短杂交时间
early[b] = DFS(b);
}
//选择最优的杂交方案
early[target] = min(early[target], max(times[a], times[b]) + max(early[a], early[b]));
}
return early[target];
}
以上便是我对这道题的看法,很高兴与大家分享。文章来源地址https://www.toymoban.com/news/detail-409334.html
到了这里,关于蓝桥杯-作物杂交(C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!