秋招算法——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攻击…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...