蓝桥练习题题解——作物杂交——Java
作物杂交(难度较高，不应该给大专的出啊)
时间限制：1.0s 内存限制：256.0MB
问题描述
作物杂交是作物栽培中重要的一步。已知有 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 类作物的种子。
输出格式
输出一个整数，表示得到目标种子的最短杂交时间。
样例输入
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≤N≤2000, 2≤M≤N, 1≤K≤100000, 1≤T≤N, 保证目标种子一定可以通过杂交得到。
题解：
package demo;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class demo {
static int aa[], dp[];
static List<Point> bh[];
public static void main(String[] args) throws IOException {
StreamTokenizer x = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
x.nextToken();
int n = (int) x.nval;
x.nextToken();
int m = (int) x.nval;
x.nextToken();
int k = (int) x.nval;
x.nextToken();
int t = (int) x.nval;
aa = new int[n + 1];
dp = new int[n + 1];
bh = new List[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
int bb[] = new int[m + 1];
for (int i = 1; i <= n; i++) {
x.nextToken();
aa[i] = (int) x.nval;
bh[i] = new ArrayList<Point>();
}
for (int i = 1; i <= m; i++) {
x.nextToken();
bb[i] = (int) x.nval;
dp[bb[i]] = 0;
}
for (int i = 0; i < k; i++) {
x.nextToken();
int xx = (int) x.nval;
x.nextToken();
int yy = (int) x.nval;
x.nextToken();
int nn = (int) x.nval;
bh[nn].add(new Point(xx, yy));
}
out.println(dfs(t));
out.flush();
}
public static int dfs(int n) {
if (dp[n] != Integer.MAX_VALUE)
return dp[n];
List<Point> p = bh[n];
for (int i = 0; i < p.size(); i++) {
int x = p.get(i).x, y = p.get(i).y;
dp[n] = Math.min(dp[n], Math.max(dfs(x), dfs(y)) + Math.max(aa[x], aa[y]));
}
return dp[n];
}
}
腾讯云开发者
