蓝桥杯算法练习系统—作物杂交【第十一届】【省赛】【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不起作用&…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...