蓝桥杯-作物杂交(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];
}

以上便是我对这道题的看法,很高兴与大家分享。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6336.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【hello C语言】结构体(下)

目录 1.结构体的声明 1.1 结构的声明 1.2 特殊声明&#xff1a;匿名结构体 1.3 结构的自引用 2. 结构体的定义和初始化 3. 结构体的内存对齐 3.1 内存对齐规则 3.2 内存对齐存在的原因 3.3 修改默认对其数 4. 结构体传参 C语言&#x1f6f4; 1.结构体的声明 结构体便是描述复杂…

一种适合容器化部署的雪花算法ID生成器

雪花算法简介 SnowFlake 中文意思为雪花&#xff0c;故称为雪花算法。最早是 Twitter 公司在其内部用于分布式环境下生成唯一 ID。 雪花算法有以下几个优点&#xff1a; 高并发分布式环境下生成不重复 id&#xff0c;每秒可生成百万个不重复 id。基于时间戳&#xff0c;以及同…

零编程经验,通过 GPT-4 十分钟开发了一个浏览器插件,并成功运行,实现了需求目标!

大佬蓝鸟ID: sundyme零编程经验&#xff0c;通过 GPT-4 十分钟开发了一个浏览器插件&#xff0c;并成功运行&#xff0c;实现了需求目标&#xff01;太不可思意了&#xff0c;真正体会到了自然语言编程的魅力&#xff01; 下一步是利用Pinterest 的 API 接口实现自动发图&#…

No.026<软考>《(高项)备考大全》【第10章】项目沟通和干系人管理(第2部分-干系人管理)

1 干系人管理部分相关 1.1 干系人ITO 1.2 干系人管理 过程过程的定义过程的作用识别干系人识别能影响项目决策、活动或结果的个人、群体或组织&#xff0c;以及被项目决策、活动或者结果影响的个人、群体或者组织&#xff0c;并分析和记录他们的相关信息的过程帮助项目经理建…

此战成硕,我成功上岸西南交通大学了~~~

友友们&#xff0c;好久不见&#xff0c;很长时间没有更一个正式点的文章了&#xff01; 是因为我在去年年底忙着准备初试&#xff0c;今年年初在准备复试&#xff0c;直到3月底拟录取后&#xff0c;终于可以写下这篇上岸贴&#xff0c;和大家分享一下考研至上岸的一个过程 文章…

游戏算法-游戏AI行为树,python实现

参考文章&#xff1a;Behavior trees for AI: How they work (gamedeveloper.com) 本文主要参考上述weizProject Zomboid 的开发者 Chris Simpson文章的概念&#xff0c;用伪代码实现代码例子 AI概述 游戏AI是对游戏内所有非玩家控制角色的行为进行研究和设计&#xff0c;使得游…

电子拣货标签9代系统简介

CK_Label_v9一、产品参数 产品型号 CK_Label_v9 LED 3&#xff08;红&黄&绿&#xff09;独立可控 供电方式 DC 24V 0.2A 通信方式 无线通信 蜂鸣器 支持 尺寸 D60 H307mm 二、革新点 配合标签拣货使用三个灯&#xff08;红黄绿&#xff09;都可以被独立控…

基于MATALB编程的BP神经网络手臂血管分类识别,基于BP神经网络的图像分类

目标 背影 BP神经网络的原理 BP神经网络的定义 BP神经网络的基本结构 BP神经网络的神经元 BP神经网络的激活函数&#xff0c; BP神经网络的传递函数 数据 神经网络参数 基于BP神经网络手臂血管识别的MATLAB代码 效果图 结果分析 展望 背影 随着人工智能的发展&#xff0c;智…

贪心算法-删数问题C++

目录 一、题目 二&#xff1a;思路 代码 运行结果 一、题目 有一个长度为n&#xff08;n < 240&#xff09;的正整数&#xff0c;从中取出k&#xff08;k < n&#xff09;个数&#xff0c;使剩余的数保持原来的次序不变&#xff0c;求这个正整数经过删数之后最小是多…

用Python绘制六种可视化图表,简直太好用了

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python资料、源码、教程: 点击此处跳转文末名片获取 可视化图表&#xff0c;有相当多种&#xff0c;但常见的也就下面几种&#xff0c;其他比较复杂一点&#xff0c;大都也是基于如下几种进行组合&#xff0c;变换出来的。 …

记录--CSS 如何实现羽化效果?

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 最近碰到这样一个问题&#xff0c;在一张封面上直接显示书名&#xff0c;可能会存在书名看不太清楚的情况(容易受到背景干扰)&#xff0c;如下 为了解决这个问题&#xff0c;设计师提了一个“究极”方…

算法 - 希尔排序

原理 首先将数组两两分组&#xff0c;分成n组数组&#xff0c;每组数组内部进行排序。再分成n/2组数组&#xff0c;每组数组内部进行排序。直至分成只剩一组&#xff0c;最后进行排序得到最后的数组。 代码 public static int[] shell(int[] arr) {int temp;for (int gra …

计算机图形学13:三维图形的几何变换

作者&#xff1a;非妃是公主 专栏&#xff1a;《计算机图形学》 博客地址&#xff1a;https://blog.csdn.net/myf_666 个性签&#xff1a;顺境不惰&#xff0c;逆境不馁&#xff0c;以心制境&#xff0c;万事可成。——曾国藩 文章目录专栏推荐专栏系列文章序一、三维图形的几…

MongoDB综述【入门指南】

写这篇博客,正好是2023年4月5日15:29:31,是清明节,放假一天,我坐在我的小小租房室内,思考着没思考到啥,哈哈哈,感觉好着急啊!看完了一本《城南旧事》,但是就是不踏实,好吧~我来写一篇最近在学的一个技术 为了更优秀的自己~奥利给!! 首先,我们从最初级小白开始(因为自己也是小白…

卷麻了,00后测试用例写的比我还好,简直无地自容.....

前言 作为一个测试新人&#xff0c;刚开始接触测试&#xff0c;对于怎么写测试用例很头疼&#xff0c;无法接触需求&#xff0c;只能根据站在用户的角度去做测试&#xff0c;但是这样情况会导致不能全方位的测试APP&#xff0c;这种情况就需要一份测试用例了&#xff0c;但是不…

倾斜实景三维建模与BIM模型处理技术

倾斜实景三维建模与BIM模型处理技术 一、研究背景 ➢ 倾斜模型 ✓ 真实纹理&#xff0c;高分辨率 ✓ 真实坐标&#xff0c;高空间精度 ✓ 快速建模&#xff0c;低建模成本 ➢ BIM设计 BIM 技术作为建筑施工行业中的新技术&#xff0c;存在于建筑的全生命周期&#xff0c;服务…

机器学习算法:K近邻(k-nearest neighbors)初探

KNN的介绍和应用 KNN&#xff08;K-Nearest Neighbor&#xff09;算法是一种基于实例的学习算法&#xff0c;也是一种常见的分类算法。 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别&#xff0c;则该样本也属于这个类别。 示例 &…

Python 3 基本数据类型,包含示例演示(初学友好)

嗨害大家好鸭~ 我是芝士❤ 有好好学习python吗&#xff1f; Python学习资料电子书 点击此处跳转文末名片获取 Python3 基本数据类型 Python 中的变量不需要声明。每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 在 Python 中&#xff0c;变量就是变量…

MATLAB 求解定积分和不定积分

本文主要介绍如何通过matlab 去求解常见的定积分和不定积分的结果&#xff0c;使用matlab 内置函数 int。 语法&#xff1a; Fint(表达式&#xff0c;变量&#xff0c;变量上下限) 目录 例子1 单变量不定积分 例子2 多变量不定积分 例子3 单变量定积分 例子4 定积分近似求…

软件测试高频出现面试题-2(实用)

每日面试1、自我介绍2、简单介绍最近项目你是如何开展测试工作的呢&#xff1f;3、描述在这个项目里面你主要负责哪些模块的测试&#xff1f;选中一个业务复杂的讲述你是如何测试的呢&#xff1f;1、自我介绍 主要可以从三个方面准备&#xff1a;我的基础信息&#xff0c;我的…
最新文章