网易首页 > 网易号 > 正文 申请入驻

程序设计实习:13.2最长上升子序列

0
分享至

动态规划 例题:灌溉草场

在一片草场上:有一条长度为L (1 <= L <= 1,000,000,L为偶数)的线 段。 John的N (1 <= N <= 1000) 头奶牛都沿着草场上这条线段吃草,每头 牛的活动范围是一个开区间(S,E),S,E都是整数。不同奶牛的活动范围可以 有重叠。 John要在这条线段上安装喷水头灌溉草场。每个喷水头的喷洒半径可以随 意调节,调节范围是 [A B ](1 <= A <= B <= 1000),A,B都是整数。要求 线段上的每个整点恰好位于一个喷水头的喷洒范围内 每头奶牛的活动范围要位于一个喷水头的喷洒范围内 任何喷水头的喷洒范围不可越过线段的两端(左端是0,右端是L ) 请问, John 最少需要安装多少个喷水头。

在位置2和6,喷水头的喷洒范围不算重叠

问题分析:

解题思路:

解题思路:

可以使用优先队列priority_queue! (multiset也可以,比 priority_queue慢一点)!

求F(X)时,若坐标属于[X-2B, X-2A]的二元组(i,F(i))都保存在 一个priority_queue中,并根据F(i)值排序,则队头的元素就能 确保是F(i)值最小的。

在求 X点的F(x)时,必须确保队列中包含所有属于 [X-2B,X-2A]的点。 而且,不允许出现坐标大于X-2A的点,因为这样的点对求F(X)无用,如 果这样的点出现在队头,因其对求后续点的F值有用,故不能抛弃之, 于是算法就无法继续了。

队列中可以出现坐标小于 X-2B 的点。这样的点若出现在队头,则直接 将其抛弃。

求出X点的F值后,将(X-2A+2, F(X-2A+2))放入队列,为求F(X+2)作准 备

队列里只要存坐标为偶数的点即可

手工实现优先队列的方法

如果一个队列满足以下条件:

1) 开始为空

2) 每在队尾加入一个元素a之前,都从现有队尾往前删除元素, 一直删到碰到小于 a的元素为止,然后再加入a 那么队列就是递增的,当然队头的元素,一定是队列中最小 的

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
第四届新时代电视节颁奖,演员张志坚凭借《狂飙》荣获最佳男配角

第四届新时代电视节颁奖,演员张志坚凭借《狂飙》荣获最佳男配角

娱乐八卦木木子
2024-04-30 13:49:14
美国布林肯:50多个国家公开支持乌克兰,1个国家秘密支持俄罗斯

美国布林肯:50多个国家公开支持乌克兰,1个国家秘密支持俄罗斯

泸沽湖
2024-05-01 00:51:05
数不清的蜘蛛!欧空局探测器在火星“古城废墟”中拍到惊悚照片

数不清的蜘蛛!欧空局探测器在火星“古城废墟”中拍到惊悚照片

星空天文
2024-04-30 07:04:40
新一代丰田卡罗拉曝光,外观造型全面升级,最快年内全球首发!

新一代丰田卡罗拉曝光,外观造型全面升级,最快年内全球首发!

户外小阿隋
2024-04-30 23:08:30
古天乐坚持十年每天只吃一顿饭,专家:挨饿有助于长寿,网友热议

古天乐坚持十年每天只吃一顿饭,专家:挨饿有助于长寿,网友热议

宇航说教育
2024-04-29 14:43:31
不稳了?韩国人金玟哉到底怎么了……

不稳了?韩国人金玟哉到底怎么了……

阿万体育
2024-05-01 12:28:52
机关食堂乱象

机关食堂乱象

据说说娱乐
2024-05-01 07:50:28
80岁老教师收到劳动节最“凡尔赛”礼物,64年教龄获吉尼斯世界纪录认证

80岁老教师收到劳动节最“凡尔赛”礼物,64年教龄获吉尼斯世界纪录认证

上游新闻
2024-05-01 11:47:28
退休后才知道,低层次的亲家常说这六种话,高层次的亲家守口如瓶

退休后才知道,低层次的亲家常说这六种话,高层次的亲家守口如瓶

布衣粗食68
2024-04-30 15:41:35
60岁大哥保持一周2次性生活,坚持一年后,结果让医生羡慕不已

60岁大哥保持一周2次性生活,坚持一年后,结果让医生羡慕不已

奇妙的本草
2024-04-29 20:00:09
章子怡突然高调宣布喜讯!这个瓜,震惊了

章子怡突然高调宣布喜讯!这个瓜,震惊了

娱乐圈酸柠檬
2024-05-02 00:02:54
毛星火微博大号被禁言

毛星火微博大号被禁言

林樾读书
2024-04-30 13:14:05
披着谍战外衣,上演一幕幕闹剧,《哈尔滨1944》终成业界笑话

披着谍战外衣,上演一幕幕闹剧,《哈尔滨1944》终成业界笑话

娱乐圈酸柠檬
2024-05-01 20:04:27
73岁老妇嫁给39岁男子,婚后生活令人羡慕,每周的性生活多达六次

73岁老妇嫁给39岁男子,婚后生活令人羡慕,每周的性生活多达六次

唐宁街上的猫
2024-04-28 16:28:34
扎心了!山东34岁大龄剩女相亲看中年薪50万上海剩男,被嫌弃太老

扎心了!山东34岁大龄剩女相亲看中年薪50万上海剩男,被嫌弃太老

狐哥讲动物
2024-04-30 11:34:48
郑家榆大婶年纪仍魅力不减!穿“火腿纹”裙复古优雅,高级感爆棚

郑家榆大婶年纪仍魅力不减!穿“火腿纹”裙复古优雅,高级感爆棚

顶牌故事会
2024-04-28 11:36:09
五一福建舰海试!揭开了两个谜题:核常混合动力与增程型航母

五一福建舰海试!揭开了两个谜题:核常混合动力与增程型航母

星辰大海路上的种花家
2024-05-01 21:13:58
黑人兄弟呀 ,太厉害了!

黑人兄弟呀 ,太厉害了!

美食阿鳕
2024-05-01 20:29:47
科学界的重大发现, 推翻了进化论, 原来人类是外星人创造的!

科学界的重大发现, 推翻了进化论, 原来人类是外星人创造的!

三农老历
2024-05-01 07:35:09
大S突然发文哭诉汪小菲,原来真相是这样的!

大S突然发文哭诉汪小菲,原来真相是这样的!

菠萝小九
2024-04-30 09:00:03
2024-05-02 04:06:44
爱你雅课
爱你雅课
科普知识,科教视频
213文章数 623关注度
往期回顾 全部

科技要闻

余承东卸任华为终端CEO 新任命为董事长

头条要闻

哥伦比亚总统宣布将与以色列断绝外交关系

头条要闻

哥伦比亚总统宣布将与以色列断绝外交关系

体育要闻

詹眉湖人:洛杉矶大型烟花秀

娱乐要闻

黄子韬被曝求婚徐艺洋 大量亲密照曝光

财经要闻

王石自动放弃2023年千万退休金

汽车要闻

预售2.89-3.49万 奔腾小马正式开启预售

态度原创

旅游
数码
艺术
手机
军事航空

旅游要闻

假期最受欢迎的小众目的地 会玩的人已经去了

数码要闻

五一如何“满电”出行?充电设备大部分人都选错了!

艺术要闻

造科幻之物于园林 “天工开悟——夏航雕塑展”于南池子美术馆呈现

手机要闻

TikTok 因绕过苹果 App Store 应用内购系统引起争议

军事要闻

近距离看中国第三艘航母福建舰解缆起航

无障碍浏览 进入关怀版