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

dedecms做门户网站今日热点新闻事件摘抄50字

dedecms做门户网站,今日热点新闻事件摘抄50字,抖音代运营协议书范本,明空网络做网站好不好问题描述 作物杂交是作物栽培中重要的一步。已知有 N 种作物(编号 1 至 N ),第 i 种作物从播种到成熟的时间为 Ti。 作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天,作物 B 种植时间为 7 天&#xff0…

问题描述

作物杂交是作物栽培中重要的一步。已知有 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; 
}

http://www.ritt.cn/news/18580.html

相关文章:

  • wordpress 用户中心厦门百度seo
  • 做艺术品拍卖的网站seo研究中心晴天
  • 微软asp.net mvc4 web企业网站开发实战课程自己如何建立网站
  • 最好的网站建设组织站长推荐
  • 国家工商网站查询网站服务器是什么意思
  • 做柱状图好看的网站百度反馈中心
  • 2021年中国十大电商平台排名优化设计的答案
  • 上海网站备案流程百度竞价排名背后的伦理问题
  • 织梦网站做关键词江北seo综合优化外包
  • 镇江公司做网站企业seo服务
  • 成人高考条件软件排名优化
  • 导航网站怎么做西安seo优化顾问
  • 做soho要不要注册网站网络推广赚钱项目
  • 网络推广培训如何商品seo优化是什么意思
  • 邯郸建移动网站费用百度注册公司地址
  • 武汉seo网站排名网站定制的公司
  • 石家庄铁路网上海搜索优化推广
  • 南京做网站建设的公司网站分析
  • 专业做网站制作自助建站系统我要推广网
  • 不用网站做淘宝客网络推广方法有哪些
  • 制作手机软件的软件北京网站优化实战
  • 学会网站开发有什么好处百度搜索榜单
  • 云南省城乡和住房建设厅网站网站建站设计
  • 绿色建筑网站方象科技的企业愿景
  • wordpress小工具制作seo搜索铺文章
  • 用dede做的网站电商seo是指
  • wordpress 音乐 插件怎么用seo是什么专业的课程
  • 网站的广告语应该怎么做百度关键词刷搜索量
  • 百度做网站吗百度广告公司
  • 东莞公司网站设计友情链接qq群