侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】作物杂交【蓝桥杯】

GabrielxD
2022-12-29 / 0 评论 / 0 点赞 / 16 阅读 / 1,454 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

作物杂交 - 蓝桥云课


作物杂交是作物栽培中重要的一步。已知有 NN 种作物 (编号 11NN ),第 ii 种作物从播种到成熟的时间为 TiT_i。作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。如作物 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, TNN 表示作物种类总数 (编号 11NN),MM 表示初始拥有的作物种子类型数量,KK 表示可以杂交的方案数,TT 表示目标种子的编号。

第 2 行包含 NN 个整数,其中第 ii 个整数表示第 ii 种作物的种植时间 Ti (1Ti100)T_i\ (1 \leq T_i \leq 100)

第 3 行包含 MM 个整数,分别表示已拥有的种子类型$ K_j\ (1 \leq K_j \leq M)$ 两两不同。

第 4 至 KK + 3 行,每行包含 3 个整数 A,B,CA, B,C,表示第 AA 类作物和第 BB 类作物杂交可以获得第 CC 类作物的种子。

其中,1N2000,2MN,1K105,1TN1 \leq N \leq 2000, 2 \leq M \leq N, 1 \leq K \leq 10^5, 1 \leq T \leq 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 天。

运行限制

  • 最大运行时间:2s
  • 最大运行内存: 256M

解题

方法一:DFS 记忆化搜索

思路

注意:一种种子可能有多种杂交配方,所以记录杂交配方时值要存一个列表,而不仅仅是单独一种配方。

自上而下递归求每种需求种子的最短时间,具体来说,需要 CC 种子:

  • 如果 CC 种子已存在,则直接返回生成 CC 种子所需的最短时间,以避免重复计算。
  • 如果 CC 种子不存在,则查询杂交生成它的所有配方,比如有 A+BCA + B \to C,则再判断 ABA、B 种子是否存在,如果不存在,递归地计算生成 ABA、B 所需的时间。那么杂交生成 CC 在该配方下所需要的时间就是 min(spent[A],spent[B])\min(spent[A], spent[B])
  • 计算完所有杂交生成 CC 的配方的所需时间后,取其中最短的时间即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, m, k, t;
    // pt: 种子的生长时间 spent: 生成该种子所需的最短时间(已存在的为0 没有的为0x3f3f3f3f)
    static int[] pt, spent;
    // 标记种子是否存在
    static boolean[] has;
    // 杂交生成的配方: { 结果种子C: [[材料种子A, 材料种子B, 杂交所需时间], [配方2], ...], ... }
    static Map<Integer, List<int[]>> mp = new HashMap<>();

    static int dfs(int c) {
        if (has[c]) return spent[c];
        for (int[] arr : mp.get(c)) {
            int a = arr[0], b = arr[1];
            if (!has[a]) dfs(a);
            if (!has[b]) dfs(b);
            spent[c] = Math.min(spent[c], arr[2] + Math.max(spent[a], spent[b]));
        }
        has[c] = true;
        return spent[c];
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        in.nextToken();
        k = (int) in.nval;
        in.nextToken();
        t = (int) in.nval;
        pt = new int[n + 1];
        spent = new int[n + 1];
        Arrays.fill(spent, 0x3f3f3f3f);
        has = new boolean[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            pt[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            has[x] = true;
            spent[x] = 0;
        }
        while (k-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            in.nextToken();
            int c = (int) in.nval;
            mp.putIfAbsent(c, new ArrayList<>());
            mp.get(c).add(new int[]{a, b, Math.max(pt[a], pt[b])});
        }
        System.out.println(dfs(t));
    }
}
0

评论区