秋招算法——AcWing101——拦截导弹
文章目录
- 题目描述
- 思路分析
- 实现源码
- 分析总结
题目描述
思路分析
- 目前是有一个笨办法,就是创建链表记录每一个最长下降子序列所对应的节点的链接,然后逐个记录所有结点的访问情况,直接所有节点都被访问过。
- 这个方法不是很好,因为需要计算很多次,会超时,这里用了贪心的方法来证明,虽然不是最优子序列,但是数量是一致的。
实现源码
#include <iostream>
#include <algorithm>
#include <sstream>using namespace std;const int K = 110;
const int N = 110;
const int H = 12000;
int h[H];
int Up[N];
int Down[N];
struct Node {int idx;Node *next;
};
bool DownAcess[N];
Node DownRecord[N]; // 记录下降节点的序列int main() {int n = 1;string line;getline(cin,line);stringstream ss(line);while(ss>>h[n]) n++;n --;int times = 0;bool endFlag = true ;
// while(endFlag){
// endFlag = false;
// times ++;
// int maxIdx = 1;
// int maxNum = 0;// 计算最长上升子序列int res = 0;for (int i = n; i >= 1; -- i) {Down[i] = 1;DownRecord[i].idx = i;// 右侧最长上升子序列for (int k = n; k > i ; --k) {if (h[k] <= h[i]){Down[i] = max(Down[i], Down[k] + 1);if (Down[i] < Down[k] + 1)DownRecord[i].next = &DownRecord[k];}}res = max(res, Down[i]);}cout<<res<<endl;
//
// for (int i = 1; i <= n; ++i) {
// if (maxNum < Down[i]) {
// maxIdx = i;
// }
// }
//
// Node *temp = &DownRecord[maxIdx];
// while(temp != NULL){
// DownAcess[temp->idx] = true;
// }
//
// for (int i = 1; i <= n; ++i) {
// if (DownAcess[i] == false) endFlag = true;
// }// }
// cout<<times<<endl;return 0;
}
// 正解
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 1005;
//int n;
//int q[N];
//int f[N],g[N]
//
//int main()
//{
// while(cin>> q[n]) n ++;
// int res = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < i; ++j) {
// if (q[j] <= q[i])
// f[i] = max(f[i],f[j] + 1);
// }
// res = max(res,f[i]);
// }
// cout<<res<<endl;
//
// int cnt = 0;
// for(int i = 0;i < n;i ++){
// int k = 0; // 维护的索引的序列
// while(k < cnt && g[k] < q[i]) k ++; // 遍历的每一个维护的最大的序列值
// g[k] = q[i];
// if(k >= cnt) cnt ++;
//
// }
//}
分析总结
- 这里的证明看的不是很懂,但是用样例推过了,确实是正确的。使用贪心求最少的子序列数量,和两次最优子序列是相同的。
- 但是如果确实想不起来,确实可以使用这个方法进行实验。
相关文章:

秋招算法——AcWing101——拦截导弹
文章目录 题目描述思路分析实现源码分析总结 题目描述 思路分析 目前是有一个笨办法,就是创建链表记录每一个最长下降子序列所对应的节点的链接,然后逐个记录所有结点的访问情况,直接所有节点都被访问过。这个方法不是很好,因为需…...

IDEA不能创建新项目和新模块
问题: IDEA不管是创建新项目还是新模块都创建不成功,会报如下图错误 解决方案: 在电脑设置里搜索 “防火墙和网络保护” ,打开如下图所示 找到你所安装的IDEA,更改设置,选中IDEA 最后,确定&am…...

WebRTC 的核心:RTCPeerConnection
WebRTC 的核心:RTCPeerConnection WebRTC 的核心:RTCPeerConnection创建 RTCPeerConnection 对象RTCPeerConnection 与本地音视频数据绑定媒体协商ICE什么是 Candidate?收集 Candidate交换 Candidate尝试连接 SDP 与 Candidate 消息的互换远端…...
LeetCode hot100-39-N
101. 对称二叉树给你一个二叉树的根节点 root , 检查它是否轴对称。做不出来哇,递归一生之敌 普通的对一棵树的递归遍历根本没办法只接比较左子树的左和右子树的右这样来比较,所以这题比较巧妙的是把这棵树当做两棵树一样去遍历比较。 官方…...
NumPy常用操作
目录 一:简介 二:NumPy 常用操作 三:总结 一:简介 是一个开源的Python库,它为Python提供了强大的多维数组对象和用于处理这些数组的函数。NumPy的核心是ndarray,它是一个高效的多维数组容器,用于存储和处理大规模的数据。NumPy还提供了许多数学函数,用于数组之间的操…...

学习笔记——字符串(单模+多模+练习题)
单模匹配 Brute Force算法(暴力) 算法思想 母串和模式串字符依次配对,如果配对成功则继续比较后面位置是否相同,如果出现匹配不成功的位置,则j(模式串当前的位置)从头开始,i&…...
DOT + graphviz 轻松画图
GraphViz:2 DOT语法和相关应用_graphviz dot-CSDN博客 图可视化之Graphviz - 知乎 Graphviz 是由AT&T Research、Lucent Bell实验室开源的可视化图形工具,可以很方便的用来绘制结构化的图形网络。具体地,其使用一种名为dot语言的DSL来编…...

使用Vue调用ColaAI Plus大模型,实现聊天(简陋版)
首先去百度文心注册申请自己的api 官网地址:LuckyCola 注册点开个人中心 查看这个文档自己申请一个ColaAI Plus定制增强大模型API | LuckyColahttps://luckycola.com.cn/public/docs/shares/api/colaAi.html来到vue的页面 写个样式 <template><Header …...

Unity使用sherpa-onnx实现离线语音合成
sherpa-onnx https://github.com/k2-fsa/sherpa-onnx 相关dll和lib库拷进Unity,官方示例代码稍作修改 using SherpaOnnx; using System; using System.IO; using System.Runtime.InteropServices; using UnityEngine;public class TTS : MonoBehaviour {public st…...

Elasticsearch入门基础和集群部署
Elasticsearch入门基础和集群部署 简介基础概念索引(Index)类型(Type)(逐步弃用)文档(Document)字段(Field)映射(Mapping)分片&#x…...
12、24年--信息系统治理——IT治理
主要考选择题,2分左右,案例、论文涉及概率不大,需要认证读课本原文。 1、IT治理基础 IT治理是描述组织采用有效的机制对信息技术和数据资源开发利用,平衡信息化发展和数字化转型过程中的风险,确保实现组织的战略目标的过程。 1.1 IT治理的驱动因素 1)存在很多问题: 信…...

Electron学习笔记(三)
文章目录 相关笔记笔记说明 五、界面1、获取 webContents 实例(1)通过窗口对象的 webContent 属性获取 webContent 实例:(2)获取当前激活窗口的 webContents 实例:(3)在渲染进程中获…...

【Redis】Redis键值存储
大家好,我是白晨,一个不是很能熬夜,但是也想日更的人。如果喜欢这篇文章,点个赞👍,关注一下👀白晨吧!你的支持就是我最大的动力!💪💪💪…...

C++系统编程篇——Linux初识(系统安装、权限管理,权限设置)
(1)linux系统的安装 双系统---不推荐虚拟机centos镜像(可以使用)云服务器/轻量级云服务器(强烈推荐) ①云服务器(用xshell连接) ssh root公网IP 然后输入password ①添加用户: addus…...

No Cortex-M SW Device Found
将DIO和CLK管脚调换一下...

提升写作效率的秘密武器:一个资深编辑的AI写作体验
有句话说:“写作是一项你坐在打字机前流血的工作。”而如今,各类生成式软件的涌现似乎打破了写作这一古老的艺术形式壁垒。过去,作家们独自在书桌前冥思苦想,如今,一款名为“玲珑AI工具”的ai写作助手正悄然改变着文案写作行业的创作生态,成为提升写作效率的秘密武器。 在传统…...

Python sort() 和 sorted() 的区别应用实例详解
大家好,今天针对 Python 中 sort() 和 sorted() 之间的区别,来一个实例详细解读。sort — 顾名思义就是排序的意思,它可以接收的对象为可迭代的数据类型。今天以列表为例子演示两者的不同点、相同点,以及其中一些常用的高级参数使…...

七、Redis三种高级数据结构-HyperLogLog
Redis HyperLogLog是用来做基数统计的算法,HyperLogLog在优点是,在输入的元素的数量或者体积非常大时,计算基数占用的空间总是固定的、并且非常小。在Redis里每个HyperLogLog键只需花费12KB内存,就可以计算接近 264 个元素的基数。…...

2024年【金属非金属矿山(露天矿山)安全管理人员】模拟考试题库及金属非金属矿山(露天矿山)安全管理人员作业模拟考试
题库来源:安全生产模拟考试一点通公众号小程序 金属非金属矿山(露天矿山)安全管理人员模拟考试题库参考答案及金属非金属矿山(露天矿山)安全管理人员考试试题解析是安全生产模拟考试一点通题库老师及金属非金属矿山&a…...

网站DDoS攻击应对策略:全面防护与恢复指南
随着互联网的发展,网络安全问题日益凸显,其中DDoS(分布式拒绝服务)攻击成为了网站安全的主要威胁之一。当网站遭受DDoS攻击时,可能会面临服务中断、性能下降、数据泄露等严重后果。因此,了解并掌握DDoS攻击…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...