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

【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+贪心)题解

题目描述 思路分析 本题有两问&#xff0c;第一问直接用lis的模板即可&#xff0c;下面重点看第二问 思路是贪心&#xff1a; 贪心流程&#xff1a; 从前往后扫描每一个数&#xff0c;对于每个数&#xff1a; 情况一&#xff1a;如果现有的子序列的结尾都小于当前的数&…...

DevicData-D-XXXXXXXX勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复

引言&#xff1a; 在数字时代&#xff0c;数据安全成为一项至关重要的挑战。DevicData-D-XXXXXXXX勒索病毒&#xff08;以下简称DevicData病毒&#xff09;是这场战斗中的新敌人&#xff0c;它能够以毁灭性的方式加密您的数据&#xff0c;迫使您在数据和时间之间做出艰难的选择…...

从入门到精通,30天带你学会C++【第七天:for循环和while循环以及数组的学习】(学不会你找我)

目录 Everyday English 前言 数组 数组的概念 数组的定义 数组的下标 for循环 循环是什么 基本格式 多重循环 while循环 do-while循环 总结 Everyday English To shine , not be illuminated. 去发光&#xff0c;而不是被照亮。 前言 好久不见&#xff0c…...

Python 编程基础 | 第五章-类与对象 | 5.2、数据成员

一、数据成员 数据成员是指类中定义的变量&#xff0c;即属性&#xff0c;根据定义位置&#xff0c;又可以分为类属性和实例属性&#xff0c;下面分别进行介绍。 1、实例属性 实例属性是指定义在类的方法中的属性&#xff0c;该属性属于当前实例&#xff0c;例如&#xff1a;…...

PHP 个人愿望众筹网站系统mysql数据库web结构apache计算机软件工程网页wamp

一、源码特点 PHP 个人愿望众筹网站系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 php 个人愿望众筹网站 代码 https://download.csdn.net/download/qq_41221322/8…...

JS--判断空值(null、undefined、NaN、false、空字符串等)

原文网址&#xff1a;JS--判断空值(null、undefined、NaN、false、空字符串等)_IT利刃出鞘的博客-CSDN博客 简介 本文介绍JavaScript判断空值的方法。 空值包括&#xff1a;undefined&#xff0c;null&#xff0c;NaN&#xff0c;&#xff0c;false&#xff0c;{}&#xff0…...

ChatGPT 背后包含了哪些技术?

ChatGPT 是由OpenAI开发的一款基于GPT-3&#xff08;Generative Pre-trained Transformer 3&#xff09;的人工智能语言模型。这个模型是使用多种编程语言和技术组合编写的。 首先&#xff0c;ChatGPT 使用了 Python 作为主要的编程语言。Python 是一种流行的高级编程语言&…...

Vue Router(二)

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

ELK整合springboot(第二课)

一、创建一个springboot的项目 pom文件如下&#xff1a; <?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个问题解决技巧大汇总!

作为运维&#xff0c;多多少少会碰见这样那样的问题或故障&#xff0c;从中总结经验&#xff0c;查找问题&#xff0c;汇总并分析故障的原因&#xff0c;这是一个运维工程师良好的习惯。每一次技术的突破&#xff0c;都经历着苦闷&#xff0c;伴随着快乐&#xff0c;可我们还是…...

解决 TensorFlow 2.x 中的 “AttributeError: module ‘tensorflow‘ has no attribute ‘placeholder‘“ 错误

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

新风机注意事项有哪些?

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

GitHub基础

1、仓库是什么意思&#xff1f;仓库拥有者是谁&#xff1f; 在软件开发或版本控制系统中&#xff0c;"仓库"&#xff08;Repository&#xff09;是指存储项目代码、配置文件、文档等相关文件的地方。它可以看作是一个中央存储库&#xff0c;用于管理和跟踪项目的各个…...

读书笔记--未来简史关键金句和阅读感悟

借着国庆假期&#xff0c;终于有时间研读了尤瓦尔.赫拉利的《未来简史》&#xff0c;作者的写作方式、文笔、观察视角都是我喜欢的类型&#xff0c;作者从古到今&#xff0c;谈到了上帝、神、宗教、科技、生物、智人到未来的超人智神&#xff08;数据主义&#xff09;&#xff…...

【Vue2.0源码学习】生命周期篇-销毁阶段(destroy)

文章目录 1. 前言2. 销毁阶段分析3. 总结 1. 前言 接下来到了生命周期流程的最后一个阶段——销毁阶段。从官方文档给出的生命周期流程图中可以看到&#xff0c;当调用了vm.$destroy方法&#xff0c;Vue实例就进入了销毁阶段&#xff0c;该阶段所做的主要工作是将当前的Vue实例…...

代理IP与Socks5代理在多领域的卓越应用

随着数字化时代的到来&#xff0c;网络工程师在跨界电商、爬虫、出海业务、网络安全和游戏等多个领域中扮演着至关重要的角色。在这些领域中&#xff0c;代理IP与Socks5代理技术已经成为网络工程师的得力助手&#xff0c;本文将深入探讨它们在技术世界中的卓越应用。 1. 跨界电…...

kafka怎么实现零拷贝(Zero-Copy)的?

Kafka 实现零拷贝&#xff08;Zero-Copy&#xff09;主要依赖于操作系统和底层网络库的支持&#xff0c;而不是特定的算法。这是因为零拷贝是一种优化数据传输的技术&#xff0c;通常是通过操作系统和硬件来实现的。以下是 Kafka 如何实现零拷贝的一般原理&#xff1a; 直接内存…...

Hive【Hive(四)函数-单行函数】

函数 函数简介 方便完成我们一些复杂的操作&#xff0c;就好像我们 Spark 中的 UDF 函数&#xff0c;避免用户反复写逻辑。 Hive 提供了大量的内置函数&#xff0c;主要可以分为以下几类&#xff1a; 单行函数聚合函数炸裂函数窗口函数 下面的命令可以查看内置函数的相关…...

C语言学生成绩录入系统

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

操作系统对内存的管理:分配与回收,虚拟内存,内存容量的扩充,内存保护,补充(链接方式、装入方式)

内存&#xff1a;即内存条&#xff0c;也称主存储器&#xff08;简称主存&#xff09;&#xff0c;用于存放数据。 为了缓和CPU和外存&#xff08;磁盘&#xff09;的速度矛盾&#xff0c;外存的程序先放入内存才能被CPU处理。 内存地址从0开始&#xff0c;每个内存地址对应一…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; 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; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

企业如何增强终端安全?

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

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

基于PHP的连锁酒店管理系统

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