蓝桥杯算法练习系统—作物杂交【第十一届】【省赛】【C组】
问题描述
作物杂交是作物栽培中重要的一步。已知有 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 类作物的种子。
输出格式
输出一个整数,表示得到目标种子的最短杂交时间。
思路:
我们改如何存储每种作物的所有杂交方案呢? 我开始想到是用二维数组存储,定义一个足够大的数组int hybrid[2005][2005],存储所有杂交方 案,如A + B->C,转换为hybrid[A][B] = C. 但是使用这种存储方案的的话,我想不到该如何去得到一种种子的最短杂交时间,因为目标种子 是数组所存的值,我们需要的是通过目标种子的标号能够得到能够杂交出该种子的所有杂交方 案! 所以这种方案肯定是不行的。
我又想出来一种通过二维向量(vector)来存储的办法。 定义一个二维向量vector< vector >hybrid(2005);存储每种作物的所有杂交方案 定义一个结构体存储杂交方案 struct parent //存储杂交方案 { int x; int y; };
每次输入一个能杂交出 x 作物的杂交方案(parent类型存储)就存入hybrid[x] 中。
#include<bits/stdc++.h>
using namespace std;
struct parent //存储杂交方案
{ int x; int y;
};
int n, m, k, t, tmp;
long long plant_time[2005];//每种作物的种植时间
bool flag[2005];//标记是否出现了该作物
long long min_hybrid_time[2005];//杂交出每种作物的最短时间
vector< vector<parent> >hybrid(2005);//存储每种作物的所有杂交方案
long long solve(int now)
{ if (flag[now])//若是已有杂交出该种作物的最短时间 return min_hybrid_time[now];//直接返回即可 for (int i = 0; i < hybrid[now].size(); i++)//对能够杂交出当前作物的方案都尝试一下 { parent tmp = hybrid[now][i];//能够杂交出当前作物的第i种方案 //当前作物的最短杂交时间是 杂交出该作物的所有方案 中的最短时间 //而每种方案的最短时间是种植其‘父母’作物所需要的时间 + 其父母作物杂交所需的的最短时
间(=两者杂交所需时间中的最大值) min_hybrid_time[now] = min(min_hybrid_time[now], max(plant_time[tmp.x],
plant_time[tmp.y]) + max(solve(tmp.x), solve(tmp.y))); } flag[now] = true;//标记已经找到最短杂交时间 return min_hybrid_time[now];//返回最短杂交时间
}
int main()
{ cin >> n >> m >> k >> t; memset(min_hybrid_time, 0x3f, sizeof(min_hybrid_time));//杂交出每种作物的最短时间初
始化为最大值memset(flag, false, sizeof(flag));//作物标记初始化 //注意作物的下标从1开始!!! for (int i = 1; i <= n; i++)//输入种植时间 cin >> plant_time[i]; for (int i = 0; i < m; i++)//输入初始种子数据 { cin >> tmp; flag[tmp] = true;//标记已经有了最短杂交时间 min_hybrid_time[tmp] = 0;//最短杂交时间 = 0,因为不需要杂交 } for (int i = 0; i < k; i++)//输入所有杂交方案 { parent temp;
cin >> temp.x >> temp.y >> tmp;
hybrid[tmp].push_back(temp);//存储杂交方案
}
solve(t);//递归求解
cout << min_hybrid_time[t] << endl;//输出杂交出目标作物的最短时间
return 0;
}
相关文章:
蓝桥杯算法练习系统—作物杂交【第十一届】【省赛】【C组】
问题描述 作物杂交是作物栽培中重要的一步。已知有 N 种作物(编号 1 至 N ),第 i 种作物从播种到成熟的时间为 Ti。 作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天,作物 B 种植时间为 7 天࿰…...

java组合模式揭秘:如何构建可扩展的树形结构
组合模式(Composite Pattern)是一种结构型设计模式,它允许将对象组合成树形结构以表示整体/部分层次结构。组合模式使得客户端可以统一对待单个对象和组合对象,从而使得客户端可以处理更复杂的结构。 组合模式的主要组成部分包括&…...

pycharm 历史版本下载地址
pycharm 历史版本下载地址 老版本能用就行,不需要搞最新的,当然了,有些小伙伴就是喜欢新的(最先吃螃蟹) 博主就不搞最新了,哈哈 上菜: https://www.jetbrains.com/pycharm/download/other.html…...

Day39:安全开发-JavaEE应用SpringBoot框架Actuator监控泄漏Swagger自动化
目录 SpringBoot-监控系统-Actuator SpringBoot-接口系统-Swagger 思维导图 Java知识点: 功能:数据库操作,文件操作,序列化数据,身份验证,框架开发,第三方组件使用等. 框架库:MyB…...

VsCode免密登录
创建本地密匙 按下WinR输入cmd,输入 ssh-keygen -t rsa然后连续回车直到结束 找到Your public key has been saved in C:\Users\Administrator/.ssh/id_rsa.pub,每个人都不一样找到密匙所在地 打开id_rsa.pub这个文件,可以用记事本打开&am…...
蓝桥杯第八届A组:分巧克力
题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 NN 块巧克力,其中第 ii 块是 HiWiHiWi 的方格组成的长方形。为了公平起见, 小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克…...

前端框架的发展史介绍框架特点
目录 1.前端框架的发展历程 2.官网、优缺点、使用场景 2.1 jQuery 2.2 AngularJS 2.3 React 2.4 Vue.js 2.5 Angular 1.前端框架的发展历程 jQuery(2006年):jQuery是一个非常流行的JavaScript库,用于简化DOM操作和事件处理…...

【MatLab】之:Simulink安装
一、内容简介 本文介绍如何在 MatLab 中安装 Simulink 仿真工具包。 二、所需原材料 MatLab R2020b(教学使用) 三、安装步骤 1. 点击菜单中的“附加功能”,进入附加功能管理器: 2. 在左侧的“按类别筛选”下选择Using Simulin…...
动手学习深度学习之环境配置
创建conda虚拟环境 下载anaconda,安装到计算机,修改镜像源到国内 show_channel_urls: true channels:- https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/pytorch/- http://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main/- http://mirrors.tu…...

【机器学习300问】35、什么是随机森林?
〇、让我们准备一些训练数据 idx0x1x2x3x4y04.34.94.14.75.5013.96.15.95.55.9022.74.84.15.05.6036.64.44.53.95.9146.52.94.74.66.1152.76.74.25.34.81 表格中的x0到x4一共有5个特征,y是目标值只有0,1两个值说明是一个二分类问题。 关于决策树相关的前置知识&am…...

用云服务器构建gpt和stable-diffusion大模型
用云服务器构建gpt和stable-diffusion大模型 一、前置知识二、用云端属于自己的聊天chatGLM3step1、项目配置step2、环境配置1、前置知识2、环境配置流程 step3、创建镜像1、前置知识2、创建镜像流程 step4、通过 Gradio 创建ChatGLM交互界面1、前置知识2、创建ChatGLM交互界面…...

备考2024年小学生古诗文大会:历年真题15题练习和独家解析
最近有家长在问如何提高小学生古诗词的知识?如何激发小学生古诗词的学习兴趣?如何提高小学古诗词的学习成绩?如何备考2024年小学生古诗文大会?...我的建议是参加每年一度的小学生古诗词大会(免费参加,无参赛…...

C++之模板
本阶段主要针对C泛型编程和ST技术做详细讲解,探讨C更深层的使用 1.1 模板的概念 模板就是建立通用的模具,大大提高复用性 模板的特点: 模板不可以直接使用,它只是一个框架 模板的通用并不是万能的 1.2 函数模板 C另一种编程思想称为 …...

Ubuntu Flask 运行 gunicorn+Nginx 部署
linux Ubuntu 下运行python 程序出现killed 原因:CPU或内存限制:在华为云上,你可能有CPU或内存使用的限制。例如,如果你使用的是一个固定大小的实例,那么超过该实例的CPU或内存限制可能会导致进程被杀死。 参考&am…...

Tuxera NTFS 2023安装使用教程 Tuxera NTFS破解版 Tuxera NTFS for Mac优惠
对于必须在Windows电脑和Mac电脑之间来回切换的Mac朋友来说,跨平台不兼容一直是一个巨大的障碍,尤其是当我们需要使用NTFS格式的硬盘在Windows和macOS之间共享文件时。因为Mac默认不支持写入NTFS磁盘。 为了解决这一问题,很多朋友会选择很便捷…...

Linux-centos如何搭建yum源仓库
1.本地搭建(无需连接外网) 1.1检查网络配置,及网络连接 打开虚拟机,点击【编辑——虚拟网络编辑器】 点击【仅主机模式】查看子网段是否和局内IP匹配 进入局内,查看网络IP是否在你上述设置的网段内,如果不…...

Vue组件中引入jQuery
两种在vue中引入jQuery的方式 1、普通html中使用jQuery 将jQuer的文件导入到项目中,然后直接使用<script src"jQuery.js"></script>即可。 <script src"jQuery.js"></script> 2、vue组件中使用jQuery 安装依赖 c…...

设计模式 --3:装扮模式
结构图 代码 #include<iostream>using namespace std;class person { public:person() {};person(string name) { this->name name; }virtual void show() {cout << "装扮的:" << this->name << endl;} private:string name; }; //装…...
element-plus中的表单校验
1. 简单校验: 1.1 在script中给出校验规则对象,主要属性名与form对象的属性名一致1.2 一个字段的校验规则可以有多个,值是一个数组,数组中的一个对象就是一条校验规则1.3 主要校验规则: 1.3.1 required:是…...

ros小问题之roslaunch tab补不全新增的功能包
在学习Gazebo这一章节时,通过catkin_create_pkg命令创建了仿真机械臂所需的软件包,创建完成后里面的内容直接拷贝了教材配套的文件,但在roslaunch时,摁tab键补不全新加的包。 重新source catkin_ws/devel/setup.bash不起作用&…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...