当前位置: 首页 > 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中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; 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&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...