【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 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...