蓝桥杯-作物杂交(C++)

这篇具有很好参考价值的文章主要介绍了蓝桥杯-作物杂交(C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

作物杂交是作物栽培中重要的一步。已知有 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号种子的杂交方案均只有一种,但实际上,可以有很多种,解题时要考虑每种方案,并取时间最短的那个。

程序代码:

# 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯官网题目:2.包子凑数

    链接: 题目点这里 首先要知道一个数学定理裴蜀定理,还有完全背包的基本运用,这里只介绍前者 也可以看一下我的个人理解,我是第一次听说这个定理,理解可能有误差。 假设gcd(a,b)=d,gcd是最大公约数的意思。即a,b的最大公约数是d ax+by=m(x,y是任意整数,可正可负) 对

    2024年01月21日
    浏览(47)
  • 蓝桥杯单片机第14届省赛客观题目+程序题目+程序题参考答案

    目录 客观题题目 程序题题目 程序题参考答案 main.h main.c Init.h Init.c SMG.h SMG.c DSQ.h DSQ.c YanShi.h YanShi.c JZKey.h JZKey.c ds1302.h ds1302.c iic.h iic.c onewire.h onewire.c LN555.h LN555.c             首先吐槽一下,花300元体验国赛的难度,是真的崩溃。          3个小时写完,2个小时改bug!

    2024年02月11日
    浏览(192)
  • 2019蓝桥杯省赛题目——“数的分解”

    目录 题目 要求 思路 最后的代码 结果 把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法? 注意交换 3 个整数的顺序被视为同一种方法,例如 1000+1001+18 和 1001+1000+18 被视为同一种。 这是一道结果填空

    2024年02月14日
    浏览(39)
  • 蓝桥杯嵌入式第十届初赛题目解析

     最近写完了嵌入式第十届初赛的题目,拿出来和大家分享,希望帮助解决一些问题。 目录 客观题  程序设计题 题目解析 CubeMX配置  代码演示  收集的一些历年的比赛客观题和解析,以及程序设计题的PDF,在这里分享给大家。  链接 :https://pan.baidu.com/s/1hTw0inSbLjX57hOtankgKw 

    2023年04月11日
    浏览(48)
  • 蓝桥杯嵌入式第十四届省赛题目解析

    前几天刚刚参加完第十四届的省赛,这届题目比我想象中的要难,其实想一想这也是应该的,以前的知识点都被摸透了,也是需要加入新的知识点了,但是我还是想说能不能别在我参加的时候加大题目难度啊。 不过听说隔壁单片机的省赛都比往年的国赛还难,这就有点离谱了

    2024年02月06日
    浏览(53)
  • 2023年第十四届蓝桥杯JAVA B组题目

    第二次参加蓝桥杯,手机再次没电导致只写了两个半小时就交了(不能重复交哎),这次带了充电宝,结果充电宝充电线中途松了,不得不说腾讯会议的耗电量真大。本博客就是刚提交后写的,可以看看时间hhh。 就做了前五道题,不过前五道题就搜索、枚举、进制就能做和一

    2023年04月09日
    浏览(39)
  • 2023蓝桥杯c/c++省赛B组题目(最全版):

    目录 A:日期统计  B: 01 串的熵 C: 冶炼金属  D: 飞机降落 E: 接龙数列 F: 岛屿个数  G: 子串简写         H: 整数删除 I: 景区导游 J: 砍树 A:日期统计     B: 01 串的熵 用Excel做比较方便,让我看看有谁?哈哈哈哈哈  答案当然就是  11027421了!!!!! C: 冶炼金属   D: 飞机

    2024年02月07日
    浏览(26)
  • 题解动态规划:蓝桥杯2022国赛B组 题解 A题目

    在这组题(蓝桥杯C/C++ B组 国赛)里面挑了几道喜欢的题目,做了一下,笔记思路如下。( 其实是我觉得能做出的题 ) 题目图片来源于:CSDN 罚时大师月色 请问2022,拆分成10个不同的正整数有多少种不同的分法。 这道题目,拿到手上的时候,第一个想法是暴力,但是,每次

    2023年04月08日
    浏览(92)
  • 数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

    目录 题目描述 输入示例 输出示例 解题思路  解题方法(C语言) 解析 有序的二叉树遍历可以用堆栈以非递归的方式实现。 例如: 假设遍历一个节点数为6的二叉树(节点数据分别为1到6)时, 堆栈操作为:push(1);push(2);push(3);pop();pop();push(4);pop()

    2024年02月07日
    浏览(45)
  • 【蓝桥杯单片机】第十二届省赛(含题目和解答代码)

    main.c  iic.c iic.h onewire.c onewire.h      

    2024年02月04日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包