秋招算法——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 ++;
//
//    }
//}
分析总结
  • 这里的证明看的不是很懂,但是用样例推过了,确实是正确的。使用贪心求最少的子序列数量,和两次最优子序列是相同的。
  • 但是如果确实想不起来,确实可以使用这个方法进行实验。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328051.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HarmonyOS开发案例:【生活健康app之获取成就】(3)

获取成就 本节将介绍成就页面。 功能概述 成就页面展示用户可以获取的所有勋章&#xff0c;当用户满足一定的条件时&#xff0c;将点亮本页面对应的勋章&#xff0c;没有得到的成就勋章处于熄灭状态。共有六种勋章&#xff0c;当用户连续完成任务打卡3天、7天、30天、50天、…

【Redis】Redis键值存储

大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#xff0c;但是也想日更的人。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4aa;&#x1f4aa;&#x1f4aa…

009.Rx(Reactive Extenstions)的关系

响应式扩展库在组成响应式系统的应用程序中发挥作用&#xff0c;它与消息驱动的概念相关。Rx不是在应用程序或服务器之间移动消息的机制&#xff0c;而是在消息到达时负责处理消息并将其沿着应用程序内部的执行链传递的机制。需要说明的是&#xff0c;即使您没有开发包含许多组…

【Java】/*逻辑控制语句和输入输出—快速总结*/

目录 前言 一、分支语句 1.1 if 语句 1.2 switch 语句 二、循环语句 2.1 while 循环 2.1.1 break 2.1.2 continue 2.2 for 循环 2.3 do_while 循环 三、逻辑语句的小结 四、Java 中的输入输出 4.1 输出到控制台 4.2 从键盘输入 前言 Java 中的逻辑控制语句和C语…

【微信小程序开发】微信小程序、大前端之flex布局方式详细解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

激光切割机价格多少钱一台?

随着科技的飞速发展&#xff0c;激光切割技术在制造业中的应用越来越广泛。它以高精度、高效率和高质量著称&#xff0c;是金属加工行业的理想选择。然而&#xff0c;对于初次接触或打算购买激光切割机的用户来说&#xff0c;最关心的问题之一就是价格。那么&#xff0c;激光切…

相机模型的内参、外参

相机模型的内参、外参 文章目录 相机模型的内参、外参1. 针孔模型、畸变模型&#xff08;内参&#xff09;2. 手眼标定&#xff08;外参&#xff09; Reference 这篇笔记主要参考&#xff1a;slam十四讲第二版&#xff08;高翔&#xff09; 相机将三维世界中的坐标点&#xff…

架构设计入门(Redis架构模式分析)

目录 架构为啥要设计Redis 支持的四种架构模式单机模式性能分析优点缺点 主从复制&#xff08;读写分离&#xff09;结构性能分析优点缺点适用场景 哨兵模式结构优点缺点应用场景 集群模式可用性和可扩展性分析单机模式主从模式哨兵模式集群模式 总结 本文主要以 Redis 为例&am…

记一次跨域问题

线上跨域问题&#xff0c;在自己配置确认没问题下&#xff0c;要及时找运维看看是不是nginx配置问题。 两个方面&#xff1a; 项目代码 nginx配置 SpringBoot 解决跨域问题的 5 种方案&#xff01; SpringBoot解决CORS跨域问题 SpringBoot-实现CORS跨域原理及解决方案

【linux-IMX6ULL-定时器-GPT-串口配置流程-思路】

目录 1. 定时器配置流程1.1 EPIT定时器简介1.2 定时器1(epit1)的配置流程1.3 配置代码(寄存器版本)1.4 定时器-配合按键消抖1.4.1 实现原理1.4.2 代码实现&#xff08;寄存器版&#xff09; 2. GPT定时器实现高精度延时2.1 延时原理分析2.2 代码实现 3. UART串口配置流程3.1 UA…

WebRTC 的核心:RTCPeerConnection

WebRTC 的核心&#xff1a;RTCPeerConnection WebRTC 的核心&#xff1a;RTCPeerConnection创建 RTCPeerConnection 对象RTCPeerConnection 与本地音视频数据绑定媒体协商ICE什么是 Candidate&#xff1f;收集 Candidate交换 Candidate尝试连接 SDP 与 Candidate 消息的互换远端…

OpenAI GPT-4o - 介绍

本文翻译整理自&#xff1a; Hello GPT-4o https://openai.com/index/hello-gpt-4o/ 文章目录 一、关于 GPT-4o二、模型能力三、能力探索四、模型评估1、文本评价2、音频 ASR 性能3、音频翻译性能4、M3Exam 零样本结果5、视觉理解评估6、语言 tokenization 六、模型安全性和局限…

相机模型,坐标变换,畸变

小孔成像模型 墨子就记录了小孔成像是倒立的。这从几何光学的角度是很好理解的&#xff1a;光沿直线传播&#xff0c;上方和下方的光线交叉&#xff0c;导致在成像平面位置互换。 小孔的大小有什么影响&#xff1f; 小孔越大&#xff0c;进光量变大了&#xff0c;但是成像平…

Stable Diffusion入门使用技巧及个人实例分享--大模型及lora篇

大家好&#xff0c;近期使用Stable Diffusion比较多&#xff0c;积累整理了一些内容&#xff0c;得空分享给大家。如果你近期正好在关注AI绘画领域&#xff0c;可以看看哦。 本文比较适合已经解决了安装问题&#xff0c;&#xff08;没有安装的在文末领取&#xff09; 在寻找合…

智能防疫电梯模拟控制系统设计-设计说明书

设计摘要&#xff1a; 本设计是基于单片机的智能防疫电梯模拟控制系统&#xff0c;主要实现了多项功能。首先&#xff0c;系统进行无接触测温&#xff0c;如果温度正常则可以启动电梯运行&#xff0c;如果温度异常则电梯会报警提示有乘客体温异常&#xff0c;电梯不会运行。其…

04、Kafka集群安装

1、准备工作 首先准备一台虚拟机&#xff0c;centos7系统&#xff0c;先在一台上配置安装后&#xff0c;最后克隆成多台机器。 1.1 安装JDK &#xff08;1&#xff09;下载JDK&#xff0c;上传到 /root/software 路径 下载地址&#xff1a;https://www.oracle.com/cn/java/…

Node.js 学习笔记 express框架

express express 使用express下载express 初体验 express 路由什么是路由1路由的使用验证的方法 2获取请求报文参数3获取路由参数4响应设置响应报文 express 中间件5中间件全局中间件路由中间件 6静态资源中间件注意事项案例 7请求体数据8防盗链实现防盗链 9路由模块化router E…

【解决】Unity Build 应用程序运行即崩溃问题

开发平台&#xff1a;Unity 2021.3.7f1c1   一、问题描述 编辑器 Build 工程结束&#xff0c;但控制台 未显示 Build completed with a result of Succeeded [时间长度] 信息。该情况下打包流程正常&#xff0c;但应用程序包打开即崩溃。   二、问题测试记录 测试1&#xf…

CSS-flex布局

目录 flex布局组成 &#xff08;flexible box弹性布局&#xff09; display属性值&#xff1a;flex justify-content (主轴对齐方式) flex-start flex-end ​编辑 flex-center space-between 侧轴对齐方式 stretch center flex-end flex-direction (修改…

【C语言】4.C语言数组(1)

文章目录 1. 数组的概念2. 一维数组的创建和初始化2.1 数组创建2.2 数组的初始化2.3 数组的类型 3. 一维数组的使用3.1 数组下标3.2 数组元素的打印3.3 数组的输⼊ 4. 一维数组在内存中的存储5. sizeof计算数组元素个数 1. 数组的概念 数组是一组相同类型元素的集合。 数组分…