【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交

这篇具有很好参考价值的文章主要介绍了【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

1、原题链接

3305. 作物杂交

2、题目描述

作物杂交是作物栽培中重要的一步。

已知有 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。

第 3 行包含 M 个整数,分别表示已拥有的种子类型 Kj,Kj 两两不同。

第 4 至 K+3 行,每行包含 3 个整数 A,B,C,表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。

输出格式

输出一个整数,表示得到目标种子的最短杂交时间。

样例解释

1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N,1≤Ti≤100,1≤Kj≤M,
保证目标种子一定可以通过杂交得到
不保证作物 A 和 B 杂交只能生成作物 C(也就是说,A×B→C 和 A×B→D 可能同时在输入中出现)
不保证作物 C 只能由作物 A 和 B 杂交生成(也就是说,A×B→D 和 A×C→D 可能同时在输入中出现)
不保证同一杂交公式不在输入中重复出现

输入样例

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

样例解释

第 1 天至第 5 天,将编号 1 与编号 2 的作物杂交,得到编号 3 的作物种子。

第 6 天至第 10 天,将编号 1 与编号 3 的作物杂交,得到编号 4 的作物种子。

第 6 天至第 9 天,将编号 2 与编号 3 的作物杂交,得到编号 5 的作物种子。

第 11 天至第 16 天,将编号 4 与编号 5 的作物杂交,得到编号 6 的作物种子。

总共花费 16 天。

二、解题报告

1、思路分析

思路来源:y总讲解视频
y总yyds

动态规划解法(spfa思想求解)
(1)dist数组含义dist[i][j]表示在杂交次数小于等于i的方法中,生成j所需花费的最小时间。
(2)按最后一次的杂交方式进行划分,最多可以分为k种。
(3)转移方程:当最后一次杂交(假设为AB杂交)确定后,要使总时间最小,则使将AB都生成所花费的时间最小即可。即 dist[i][j]=max(dist[i-1][A],dist[i-1][B])+max(T[A],T[B])T[i]代表生成i需要花费的时间)。
(4)利用spfa进行优化:只有一个点被更新过才需要利用它来更新其他点,并且dist[][]的第一维可以被优化。
(5)利用上述思路进行模拟即可,输出dist[t]即为答案。

2、时间复杂度

时间复杂度为O(n*k)文章来源地址https://www.toymoban.com/news/detail-411980.html

3、代码详解

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2010,M=200010;   //N代表点数(作物数),M代表边数,每种作物最多可能有k种杂交方式,所以M开成N*k数量级
int h[N],e[M],ne[M],w[N],target[M],idx;  //类似邻接表存储所有的杂交方式,w[]存储生成每种作物需要花费的时间,target[i]存储利用i杂交可以生成的目标种子,w[i]存储生成i需要的时间
int n,m,k,t;
int dist[N];
bool st[N];
queue<int> q;
//类似邻接表加边
void add(int a,int b,int c){
    e[idx]=b;
    target[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
//spfa思路来填充dist数组
void spfa(){
    while(!q.empty()){
        int A=q.front();
        q.pop();
        st[A]=false;
        for(int i=h[A];i!=-1;i=ne[i]){
            int B=e[i],T=target[i];
          if(dist[T]>max(dist[A],dist[B])+max(w[A],w[B])){
             dist[T]=max(dist[A],dist[B])+max(w[A],w[B]);
             if(!st[T]){
                st[T]=true;
                q.push(T);
            }
        }
    }
    }
}

int main(){
    cin>>n>>m>>k>>t;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    memset(dist,0x3f,sizeof dist);
    while(m--){
        int x;
        cin>>x;
        dist[x]=0;           //初始作物已有,不需要生成,所以生成时间为0
        st[x]=true;
        q.push(x);
    }
    while(k--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);     //因为填充dist[a]和dist[b]时都需要知道利用它的杂交方式,所以得是无向边,便于访问          
        add(b,a,c);
    }
    spfa();
    cout<<dist[t];
    return 0;
}

三、知识风暴

Spfa算法

  • spfa算法为队列优化的Bellman-Ford算法。
  • 基本思想:在Bellman-Ford算法基础上,不是每次都进行松弛操作(如果存在边(a,b,c),即ab的边且边权为c,而且dist[a]>dist[b]+cdist[i]存储1号点到i号点的最短路径的长度)即可进行松弛),而是如果一个点被更新过,将它加入队列中,然后利用它来松弛其他点,然后将该点弹出,再将更新过的点加入队列中,循环往复,直到队列为空,算法结束。

到了这里,关于【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Acwing 897. 最长公共子序列 (每日一题)

    给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数 N和 M。 第二行包含一个长度为 N 的字符串,表示字符串 A。 第三行包含一个长度为 M 的字符串,表示字符串 B。 字符串均由小写字母构成

    2024年02月10日
    浏览(34)
  • AcWing 898. 数字三角形 (每日一题)

    像数组下标 出现 i-1 的,在循环的时候从 i=1 开始。 0x3f3f3f3f : 1061109567 Integer.MAX_VALUE : 2147483647 在选用 Integer.MAX_VALUE 时,很可能会出现 数据溢出 。 所以在用 Integer.MAX_VALUE 时 需要先取 MAX 再加 a[i][j]; 注:做 数字三角形 这题时, 初始化时需要注意一下边界 。 由于我们 状态计

    2024年02月11日
    浏览(39)
  • 蓝桥杯每日一题----货物摆放

    上来一看,三个for循环,从1到n,寻找满足l w h=n的个数,但是这样根本跑不出来答案,n太大了,1e15的级别,O(n)的时间复杂度都不行,更何况是O(n^3)。 尝试降低时间复杂度很难,可以尝试降低数据规模。 插入理论:影响代码运行时间的两个因素算法时间复杂度和数据规

    2024年01月21日
    浏览(40)
  • (蓝桥杯每日一题)love

    问题描述 马上就要到七夕情人节了,小蓝在这天想要心爱得男神表白,于是她写下了一个长度为n仅由小写字母组成的字符串。 她想要使这个字符串有 1314个 love 子序列但是马虎的小蓝却忘记了当前已经有多少个子序列为 love。 请你帮小蓝计算出当前字符串有多少个子序列为

    2024年01月21日
    浏览(44)
  • (蓝桥杯每日一题)字符串排序

    本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小蓝要把一个字符串中的字母按其在字母表中的顺序排列 例如,LANQIAO 排列后为AAILNOQ 又如, GOODGOODSTUDYDAYDAYUP 排后为AADDDDDGGOOOOPSTUUYYY 请问对于以下字符串,排列之后字符串是什么? WHERETHEREISA

    2024年01月21日
    浏览(39)
  • 【C语言蓝桥杯每日一题】——排列字母

    TOC     😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话

    2023年04月09日
    浏览(44)
  • 蓝桥杯每日一题----单调栈和单调队列

    单调栈即栈内的元素是单调递减或者单调递增的,我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 n 的整数数列 a 1 … a n a_1…a_n a 1 ​ … a n ​ 。 定义函数 f ( i ) f(i) f ( i ) 代表数列中第 i 个元素之后第一个大于 a i a_i a i ​ 的元素的下标,即 f ( i ) = m i n i

    2024年02月19日
    浏览(40)
  • 【C语言蓝桥杯每日一题】——等差数列

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2023年04月09日
    浏览(78)
  • 蓝桥杯每日一题002 不同子串(set用法)

    【问题描述】     一个字符串的非空子串是指字符串中长度至少为1的连续的一段字符组成的串。例如,字符串 aaab 有非空子串 a,b,aa,ab,aaa,aab,aaab,一共 7 个。 注意在计算时,只算本质不同的串的个数。 请问,字符串 0100110001010001 有多少个不同的非空子串?     

    2024年01月21日
    浏览(38)
  • 【迎战蓝桥】 算法·每日一题(详解+多解)-- day5

    🤞目录🤞 💖1. 数组中出现次数超过一半的数字 💖2. 二进制中1的个数 💖3. 替换空格 【大家好,我是 爱干饭的猿 ,如果喜欢这篇文章, 点个赞 👍, 关注一下吧, 后续会一直分享题目与算法思路 】 描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长

    2023年04月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包