【Acwing1010】拦截导弹(LIS+贪心)题解
题目描述
思路分析
本题有两问,第一问直接用lis的模板即可,下面重点看第二问
思路是贪心:
贪心流程:
从前往后扫描每一个数,对于每个数:
情况一:如果现有的子序列的结尾都小于当前的数,则创建子序列
情况二:将当前的数放到结尾大于等于它的最小的子序列后面
举个例子:
360 322 555 222.....
从左到右遍历上面序列,当遍历到222的时候,此时已经存在了两个子序列“360 322”和“555”,两个子序列的结尾分别是322和555,其中322是大于等于222且是“322和555”中最小的数,所以把222放在序列“360 322”的后边!
贪心证明:
A表示贪心算法得到的序列个数,B表示最优解
B<=A 显然
如何证明B>=A?利用调整法:
如上图所示,假设a的后面是利用贪心算法插入的一个数,b的后面是最优解插入的一个数
在这两个序列后面补齐之后:
因为a是最优解的插法,所以b>=a
可以把x及后面的序列做交换,导致最优解变成了贪心解,并且总序列个数不变,所以B>=A
完整代码:
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
const int N=1010;
int f[N],h[N],q[N];
int cnt,res;
int n;
int main()
{string str;getline(cin,str);stringstream ssin(str);while(ssin>>q[n])n++;for(int i=0;i<n;i++){f[i]=1;for(int j=0;j<i;j++)if(q[j]>=q[i])f[i]=max(f[j]+1,f[i]);res=max(res,f[i]);int k=0;while(k<cnt&&h[k]<q[i])k++;if(k<cnt)h[k]=q[i];elseh[cnt++]=q[i];}cout<<res<<endl<<cnt<<endl;return 0;
}
相关文章:

【Acwing1010】拦截导弹(LIS+贪心)题解
题目描述 思路分析 本题有两问,第一问直接用lis的模板即可,下面重点看第二问 思路是贪心: 贪心流程: 从前往后扫描每一个数,对于每个数: 情况一:如果现有的子序列的结尾都小于当前的数&…...

DevicData-D-XXXXXXXX勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复
引言: 在数字时代,数据安全成为一项至关重要的挑战。DevicData-D-XXXXXXXX勒索病毒(以下简称DevicData病毒)是这场战斗中的新敌人,它能够以毁灭性的方式加密您的数据,迫使您在数据和时间之间做出艰难的选择…...

从入门到精通,30天带你学会C++【第七天:for循环和while循环以及数组的学习】(学不会你找我)
目录 Everyday English 前言 数组 数组的概念 数组的定义 数组的下标 for循环 循环是什么 基本格式 多重循环 while循环 do-while循环 总结 Everyday English To shine , not be illuminated. 去发光,而不是被照亮。 前言 好久不见,…...
Python 编程基础 | 第五章-类与对象 | 5.2、数据成员
一、数据成员 数据成员是指类中定义的变量,即属性,根据定义位置,又可以分为类属性和实例属性,下面分别进行介绍。 1、实例属性 实例属性是指定义在类的方法中的属性,该属性属于当前实例,例如:…...

PHP 个人愿望众筹网站系统mysql数据库web结构apache计算机软件工程网页wamp
一、源码特点 PHP 个人愿望众筹网站系统是一套完善的web设计系统,对理解php编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。 php 个人愿望众筹网站 代码 https://download.csdn.net/download/qq_41221322/8…...
JS--判断空值(null、undefined、NaN、false、空字符串等)
原文网址:JS--判断空值(null、undefined、NaN、false、空字符串等)_IT利刃出鞘的博客-CSDN博客 简介 本文介绍JavaScript判断空值的方法。 空值包括:undefined,null,NaN,,false,{}࿰…...

ChatGPT 背后包含了哪些技术?
ChatGPT 是由OpenAI开发的一款基于GPT-3(Generative Pre-trained Transformer 3)的人工智能语言模型。这个模型是使用多种编程语言和技术组合编写的。 首先,ChatGPT 使用了 Python 作为主要的编程语言。Python 是一种流行的高级编程语言&…...

Vue Router(二)
目录 一、嵌套路由 1、路由定义 2、代码例子 3、重定向 二、懒加载 1、缘由 2、代码例子 三、导航守卫 1、全局前置守卫 2、全局后置守卫 3、meta元信息 四、生命周期 1、解释 2、执行顺序 3、例子 五、keep-alive组件缓存(保活) 1、介…...

ELK整合springboot(第二课)
一、创建一个springboot的项目 pom文件如下: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLo…...
运维常见的22个故障排查和10个问题解决技巧大汇总!
作为运维,多多少少会碰见这样那样的问题或故障,从中总结经验,查找问题,汇总并分析故障的原因,这是一个运维工程师良好的习惯。每一次技术的突破,都经历着苦闷,伴随着快乐,可我们还是…...

解决 TensorFlow 2.x 中的 “AttributeError: module ‘tensorflow‘ has no attribute ‘placeholder‘“ 错误
项目场景: 在使用 TensorFlow 框架实现深度学习应用时,可能会遇到以下错误: AttributeError: module tensorflow has no attribute placeholder问题描述 在 TensorFlow 1.x 版本中,placeholder 函数用于创建占位符张量。然而&a…...

新风机注意事项有哪些?
选择和使用新风机时,有几个关键注意事项需要牢记: 安装位置:新风机的安装位置很重要。通常情况下,应将其安装在室外以避免室内产生噪音和减少室内的体积占据。确保选择合适的安装位置,以便新风机能够顺利引入新鲜空气。…...

GitHub基础
1、仓库是什么意思?仓库拥有者是谁? 在软件开发或版本控制系统中,"仓库"(Repository)是指存储项目代码、配置文件、文档等相关文件的地方。它可以看作是一个中央存储库,用于管理和跟踪项目的各个…...
读书笔记--未来简史关键金句和阅读感悟
借着国庆假期,终于有时间研读了尤瓦尔.赫拉利的《未来简史》,作者的写作方式、文笔、观察视角都是我喜欢的类型,作者从古到今,谈到了上帝、神、宗教、科技、生物、智人到未来的超人智神(数据主义)ÿ…...

【Vue2.0源码学习】生命周期篇-销毁阶段(destroy)
文章目录 1. 前言2. 销毁阶段分析3. 总结 1. 前言 接下来到了生命周期流程的最后一个阶段——销毁阶段。从官方文档给出的生命周期流程图中可以看到,当调用了vm.$destroy方法,Vue实例就进入了销毁阶段,该阶段所做的主要工作是将当前的Vue实例…...
代理IP与Socks5代理在多领域的卓越应用
随着数字化时代的到来,网络工程师在跨界电商、爬虫、出海业务、网络安全和游戏等多个领域中扮演着至关重要的角色。在这些领域中,代理IP与Socks5代理技术已经成为网络工程师的得力助手,本文将深入探讨它们在技术世界中的卓越应用。 1. 跨界电…...
kafka怎么实现零拷贝(Zero-Copy)的?
Kafka 实现零拷贝(Zero-Copy)主要依赖于操作系统和底层网络库的支持,而不是特定的算法。这是因为零拷贝是一种优化数据传输的技术,通常是通过操作系统和硬件来实现的。以下是 Kafka 如何实现零拷贝的一般原理: 直接内存…...
Hive【Hive(四)函数-单行函数】
函数 函数简介 方便完成我们一些复杂的操作,就好像我们 Spark 中的 UDF 函数,避免用户反复写逻辑。 Hive 提供了大量的内置函数,主要可以分为以下几类: 单行函数聚合函数炸裂函数窗口函数 下面的命令可以查看内置函数的相关…...

C语言学生成绩录入系统
一、系统概述 该系统是一个由链表创建主菜单的框架,旨在快速创建学生成绩录入系统的主菜单结构。其主要任务包括: 实现链表的创建、插入和遍历功能,用于存储和展示学生成绩录入系统各个模块的菜单项。 2. 提供用户友好的主菜单界面…...

操作系统对内存的管理:分配与回收,虚拟内存,内存容量的扩充,内存保护,补充(链接方式、装入方式)
内存:即内存条,也称主存储器(简称主存),用于存放数据。 为了缓和CPU和外存(磁盘)的速度矛盾,外存的程序先放入内存才能被CPU处理。 内存地址从0开始,每个内存地址对应一…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...