动态规划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…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
