动态规划DP 最长上升子序列模型 导弹防御模型(题目分析+C++完整代码实现)
概览检索
动态规划DP 最长上升子序列模型
导弹防御系统
原题链接
AcWiing 187. 导弹防御系统
题目描述
为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为 3和高度为 4的两发导弹,那么接下来该系统就只能拦截高度大于 4的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例,第一行包含整数 n,表示来袭导弹数量。
第二行包含 n个不同的整数,表示每个导弹的高度。
当输入测试用例 n=0时,表示输入终止,且该用例无需处理。
输出格式
对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。
数据范围
1≤n≤50
输入样例:
5
3 5 2 4 1
0
输出样例:
2
样例解释
对于给出样例,最少需要两套防御系统。
一套击落高度为 3,4的导弹,另一套击落高度为 5,2,1的导弹。
题目分析
DFS暴搜+最长上升子序列模型
最长上升子序列模型部分参考 拦截导弹。
完整代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=55;
int n;
int a[N];
int up[N],down[N];
int ans;
/*DFS+暴搜*/
//su为拦截上升高度的系统数,sd为拦截下降高度的系统数
void dfs(int u,int su,int sd){//当前解比当前全局最优解ans大,直接returnif(su+sd>=ans) return;//如果遍历到最后一个数值,计算结束,returnif(u==n){ans=su+sd;return;}//情况1:将当前数放到上升子序列中int k=0;while(k<su&&up[k]>=a[u]) k++; //找到一个序列结尾数小于当前数的序列int t=up[k]; //t保存原先序列结尾数up[k]=a[u]; //将当前数放在该序列后,更新结尾数if(k<su) dfs(u+1,su,sd); //找到了符合条件的序列else dfs(u+1,su+1,sd); //未找到符合条件的序列,新建序列,序列数su+1up[k]=t; //回溯为原先状态//情况2:将当前数放到下降子序列中k=0;while(k<sd&&down[k]<=a[u]) k++;t=down[k];down[k]=a[u];if(k<sd) dfs(u+1,su,sd);else dfs(u+1,su,sd+1);down[k]=t;
}
int main(){while(cin>>n,n){for(int i=0;i<n;i++) cin>>a[i];ans=n;dfs(0,0,0);cout<<ans<<endl;}return 0;
}
相关文章:
动态规划DP 最长上升子序列模型 导弹防御模型(题目分析+C++完整代码实现)
概览检索 动态规划DP 最长上升子序列模型 导弹防御系统 原题链接 AcWiing 187. 导弹防御系统 题目描述 为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。 例如࿰…...
LevelDB 源码阅读:写入键值的工程实现和优化细节
读、写键值是 KV 数据库中最重要的两个操作,LevelDB 中提供了一个 Put 接口,用于写入键值对。使用方法很简单: leveldb::Status status leveldb::DB::Open(options, "./db", &db); status db->Put(leveldb::WriteOptions…...
药店药品销售管理系统的设计与实现
标题:药店药品销售管理系统的设计与实现 内容:1.摘要 摘要:本文介绍了药店药品销售管理系统的设计与实现。该系统旨在提高药店的运营效率和管理水平,通过信息化手段实现药品销售、库存管理、财务管理等功能。本文详细阐述了系统的需求分析、设计思路、技…...
人格分裂(交互问答)-小白想懂Elasticsearch
通过交互式追问了解一个中间件 ? 啥是Elasticsearch ! 分布式搜索和分析引擎 ? 为啥是分布式搜索,单体难道用不了吗 ? 实际上是说这个东西可以分布式部署 ! 单机可用但扩展性差,分布式通过分片、副本和负载均衡实现海量数据存储与高并发处理 ? 提…...
【论文投稿-第八届智能制造与自动化学术会议(IMA 2025)】HTML, CSS, JavaScript:三者的联系与区别
大会官网:www.icamima.org 目录 前言 一、HTML(超文本标记语言):网页的骨架 HTML 的作用: 例子: 总结: 二、CSS(层叠样式表):网页的外观设计 CSS 的…...
python | OpenCV小记(一):cv2.imread(f) 读取图像操作(待更新)
python | OpenCV小记(一):cv2.imread(f)读取图像操作 1. 为什么 [:, :, 0] 提取的是第一个通道(B 通道)?OpenCV 的通道存储格式索引操作 [:, :, 0] 的解释常见误解 1. 为什么 [:, :,…...
网络工程师 (9)文件管理
一、树形目录结构 (一)定义与构成 树形目录结构由一个根目录和若干层子文件夹(或称为子目录)组成,它像一棵倒置的树。这棵树的根称为根文件夹(也叫根目录),从根向下,每一…...
Java中的线程池参数(详解)
public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler) {} 此构造方法的参数如下: int corePoolSize&…...
2 MapReduce
2 MapReduce 1. MapReduce 介绍1.1 MapReduce 设计构思 2. MapReduce 编程规范3. Mapper以及Reducer抽象类介绍1.Mapper抽象类的基本介绍2.Reducer抽象类基本介绍 4. WordCount示例编写5. MapReduce程序运行模式6. MapReduce的运行机制详解6.1 MapTask 工作机制6.2 ReduceTask …...
如何用函数去计算x年x月x日是(C#)
如何用函数去计算x年x月x日是? 由于现在人工智能的普及,我们往往会用计算机去算,或者去记录事情 1.计算某一年某一个月有多少天 2.计算某年某月某日是周几 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threadin…...
开发过程中如何减少属性注释?
一、注释冗余 举个例子,我们在开发项目中肯定会有状态字段,现在有个工单状态枚举 StatusEnum.java package cn.zxj.note;/*** author: Administrator* since: 2025/1/30 14:40* description:*/ public enum StatusEnum {TO_BE_SUBMITTED(1,"待提交…...
NX/UG二次开发—CAM—快速查找程序参数名称
使用UF_PARAM_XXX读取或设置参数时,会发现程序中有一个INT类型参数param_index,这个就是对应程序中的参数,比如读取程序余量,则param_index = UF_PARAM_STOCK_PART,读取程序的加工坐标系则param_index = UF_PARAM_MCS等等。 你需要读取什么参数,只要只能在uf_param_indic…...
socket实现HTTP请求,参考HttpURLConnection源码解析
背景 有台服务器,网卡绑定有2个ip地址,分别为: A:192.168.111.201 B:192.168.111.202 在这台服务器请求目标地址 C:192.168.111.203 时必须使用B作为源地址才能访问目标地址C,在这台服务器默认…...
访问CMOS RAM
实验内容、程序清单及运行结果 访问CMOS RAM(课本实验14) 代码如下: assume cs:code data segment time db yy/mm/dd hh:mm:ss$ ;int 21h 显示字符串,要求以$结尾 table db 9,8,7,4,2,0 ;各时间量的存放单元 data ends cod…...
解决AnyConnect开机自启动问题
文章目录 一、问题描述二、解决方案 (Windows)1.开启-设置2.点击“应用”3.点击“启动”,选择“关” 三、参考文章 一、问题描述 学校指定的VPN总是开机自启动,然而 设置-Preferences 中却没有取消开机自启的选项。 似乎开机自启是必然的,我…...
芯片AI深度实战:进阶篇之vim内verilog实时自定义检视
【痛点】 传统Verilog开发中,工程师不断"编码→仿真→查错"的循环。本文整合AST解析与Vim编辑器,在编码阶段即实现: ✔️ 自动标记逻辑问题 ✔️ AI+ 发现涉及多模块逻辑错误 ✔️ 强制代码风格 【解决方案】 1️⃣ 基于AST的精准模式匹配 - 深度集成…...
数据结构实战之线性表(一)
一.线性表的定义和特点 线性表的定义 线性表是一种数据结构,它包含了一系列具有相同特性的数据元素,数据元素之间存在着顺序关系。例如,26个英文字母的字符表 ( (A, B, C, ....., Z) ) 就是一个线性表,其中每个字母就是一个数据…...
jdk8项目升级到jdk17——岁月云实战
由于很早之前就升级springboot版本到2.7.9,以前做好了铺垫,相对升级要容易一些。 1 项目打包成exe 1.1 jpackage打包jar C:\Users\39305\Desktop\数量核对>jpackage ^ More? --type exe ^ More? --name zp-server ^ More? --input C:\Use…...
商品列表及商品详情展示
前言 本文将展示一段结合 HTML、CSS 和 JavaScript 的代码,实现了一个简单的商品展示页面及商品详情,涵盖数据获取、渲染、搜索及排序等功能。 效果展示 点击不同的商品会展示对应的商品详情。 代码部分 代码总体实现 <!DOCTYPE html> <htm…...
使用where子句筛选记录
默认情况下,SearchCursor将返回一个表或要素类的所有行.然而在很多情况下,常常需要某些条件来限制返回行数. 操作方法: 1.打开IDLE,加载先前编写的SearchCursor.py脚本 2.添加where子句,更新SearchCursor()函数,查找记录中有<>文本的<>字段 with arcpy.da.Searc…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
