当前位置: 首页 > news >正文

蓝桥杯算法练习系统—作物杂交【第十一届】【省赛】【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 )&#xff0c;第 i 种作物从播种到成熟的时间为 Ti。 作物之间两两可以进行杂交&#xff0c;杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天&#xff0c;作物 B 种植时间为 7 天&#xff0…...

java组合模式揭秘:如何构建可扩展的树形结构

组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许将对象组合成树形结构以表示整体/部分层次结构。组合模式使得客户端可以统一对待单个对象和组合对象&#xff0c;从而使得客户端可以处理更复杂的结构。 组合模式的主要组成部分包括&…...

pycharm 历史版本下载地址

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

Day39:安全开发-JavaEE应用SpringBoot框架Actuator监控泄漏Swagger自动化

目录 SpringBoot-监控系统-Actuator SpringBoot-接口系统-Swagger 思维导图 Java知识点&#xff1a; 功能&#xff1a;数据库操作&#xff0c;文件操作&#xff0c;序列化数据&#xff0c;身份验证&#xff0c;框架开发&#xff0c;第三方组件使用等. 框架库&#xff1a;MyB…...

VsCode免密登录

创建本地密匙 按下WinR输入cmd&#xff0c;输入 ssh-keygen -t rsa然后连续回车直到结束 找到Your public key has been saved in C:\Users\Administrator/.ssh/id_rsa.pub&#xff0c;每个人都不一样找到密匙所在地 打开id_rsa.pub这个文件&#xff0c;可以用记事本打开&am…...

蓝桥杯第八届A组:分巧克力

题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 NN 块巧克力&#xff0c;其中第 ii 块是 HiWiHi​Wi 的方格组成的长方形。为了公平起见&#xff0c; 小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克…...

前端框架的发展史介绍框架特点

目录 1.前端框架的发展历程 2.官网、优缺点、使用场景 2.1 jQuery 2.2 AngularJS 2.3 React 2.4 Vue.js 2.5 Angular 1.前端框架的发展历程 jQuery&#xff08;2006年&#xff09;&#xff1a;jQuery是一个非常流行的JavaScript库&#xff0c;用于简化DOM操作和事件处理…...

【MatLab】之:Simulink安装

一、内容简介 本文介绍如何在 MatLab 中安装 Simulink 仿真工具包。 二、所需原材料 MatLab R2020b&#xff08;教学使用&#xff09; 三、安装步骤 1. 点击菜单中的“附加功能”&#xff0c;进入附加功能管理器&#xff1a; 2. 在左侧的“按类别筛选”下选择Using Simulin…...

动手学习深度学习之环境配置

创建conda虚拟环境 下载anaconda&#xff0c;安装到计算机&#xff0c;修改镜像源到国内 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个特征&#xff0c;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题练习和独家解析

最近有家长在问如何提高小学生古诗词的知识&#xff1f;如何激发小学生古诗词的学习兴趣&#xff1f;如何提高小学古诗词的学习成绩&#xff1f;如何备考2024年小学生古诗文大会&#xff1f;...我的建议是参加每年一度的小学生古诗词大会&#xff08;免费参加&#xff0c;无参赛…...

C++之模板

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

Ubuntu Flask 运行 gunicorn+Nginx 部署

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

Tuxera NTFS 2023安装使用教程 Tuxera NTFS破解版 Tuxera NTFS for Mac优惠

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

Linux-centos如何搭建yum源仓库

1.本地搭建&#xff08;无需连接外网&#xff09; 1.1检查网络配置&#xff0c;及网络连接 打开虚拟机&#xff0c;点击【编辑——虚拟网络编辑器】 点击【仅主机模式】查看子网段是否和局内IP匹配 进入局内&#xff0c;查看网络IP是否在你上述设置的网段内&#xff0c;如果不…...

Vue组件中引入jQuery

两种在vue中引入jQuery的方式 1、普通html中使用jQuery 将jQuer的文件导入到项目中&#xff0c;然后直接使用<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. 简单校验&#xff1a; 1.1 在script中给出校验规则对象&#xff0c;主要属性名与form对象的属性名一致1.2 一个字段的校验规则可以有多个&#xff0c;值是一个数组&#xff0c;数组中的一个对象就是一条校验规则1.3 主要校验规则&#xff1a; 1.3.1 required&#xff1a;是…...

ros小问题之roslaunch tab补不全新增的功能包

在学习Gazebo这一章节时&#xff0c;通过catkin_create_pkg命令创建了仿真机械臂所需的软件包&#xff0c;创建完成后里面的内容直接拷贝了教材配套的文件&#xff0c;但在roslaunch时&#xff0c;摁tab键补不全新加的包。 重新source catkin_ws/devel/setup.bash不起作用&…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...