拦截导弹 & 导弹防御系统

这篇具有很好参考价值的文章主要介绍了拦截导弹 & 导弹防御系统。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拦截导弹

题目链接:acwing1010. 拦截导弹
题目描述:
拦截导弹 & 导弹防御系统
输入输出:
拦截导弹 & 导弹防御系统
分析:
第一个问题为输出最长递减子序列,由于导弹数在1000以内所以采用时间复杂度为 O ( n 2 ) O(n^2) O(n2)或者 O ( n l o g n ) O(nlogn) O(nlogn)的算法都可以。
第二个问题,可以用贪心的思想来做,每次新到的导弹,我们用当前导弹高度恰好大于等于该导弹高度的导弹系统去拦截,这样所用的导弹系统的数量是最少的。

我这里求最长上升子序列和贪心的时间复杂度都为 O ( n l o g n ) O(nlogn) O(nlogn)
代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1100;

int f[N];
int p[N];
int q[N];
int binary_search(int l,int r,int x){
    int mid;
    while(l<r){
        int mid=l+r>>1;
        if(p[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
int binary_search_len(int l,int r,int x){
    int mid;
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]>x) r=mid;
        else l=mid+1;
    }
    return r;
}
int main(){
    int n=0;
    while(scanf("%d",&f[n+1])!=EOF) n++;
    int k=0;
    for(int i=n;i>=1;i--){
        if(k==0||f[i]>=q[k]) q[++k]=f[i];
        else{
            int t=binary_search_len(1,k,f[i]);
            q[t]=f[i];
        }
    }
    printf("%d\n",k);
    
    k=0;
    for(int i=1;i<=n;i++){
        if(!k||p[k]<f[i]) p[++k]=f[i];
        else{
            int t=binary_search(1,k,f[i]);
            p[t]=f[i];
        }
    }
    printf("%d\n",k);
    return 0;
}

导弹防御系统

题目链接:acwing1010. 导弹防御系统
题目描述:
拦截导弹 & 导弹防御系统
输入输出:
拦截导弹 & 导弹防御系统
**分析:**这道题稍微复杂一些,因为有两种拦截导弹的可能,由于数据范围较小,可以直接暴力枚举每一种可能, d f s + 剪枝 dfs+剪枝 dfs+剪枝就行。
代码如下:文章来源地址https://www.toymoban.com/news/detail-416613.html

/*dfs+剪枝*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=55;

int n,f[N];
int up[N],down[N];
int ans;
void dfs(int u,int p,int d){//分别表示递归到哪个元素,up元素个数,down的元素个数
    if(p+d>=ans) return;//剪枝
    if(u==n){
        ans=p+d;
        return;
    }
    //down
    int k=0;
    while(k<p&&up[k]<=f[u]) k++;
    int t=up[k];
    up[k]=f[u];
    if(k<p) dfs(u+1,p,d);
    else dfs(u+1,p+1,d);
    up[k]=t;
    //up
    k=0;
    while(k<d&&down[k]>=f[u]) k++;
    t=down[k];
    down[k]=f[u];
    if(k<d) dfs(u+1,p,d);
    else dfs(u+1,p,d+1);
    down[k]=t;
}
int main(){
    
    while(cin>>n,n){
        for(int i=0;i<n;i++) scanf("%d",&f[i]);
        ans=n;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}

到了这里,关于拦截导弹 & 导弹防御系统的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 长春理工大学第六届CTF网络攻防大赛题解(文末有题目下载链接)

    此题解仅为部分题解,包括: 【RE】:①Reverse_Checkin ②SimplePE ③EzGame 【Web】①f12 ②ezrunner 【Crypto】①MD5 ②password ③看我回旋踢 ④摩丝 【Misc】①爆爆爆爆 ②凯撒大帝的三个秘密 ③你才是职业选手 ① Reverse Checkin: 双击文件看到如上提示:“也许你能从字符串里找到什么”

    2024年02月05日
    浏览(62)
  • MissileDatcom 导弹气动计算

    Missile Datcom 软件的全称为 Missile Data Compendium ,是由 美国空军飞行力学实验室 开发的一款气动力工程计算软件。弹道计算时需要获得弹体在不同马赫数、海拔、速度…条件下飞行时的气动力系数。 一般可以使用 数值算法 和 工程算法 两种方式,(1) 数值算法 利用 Fluent、

    2024年02月02日
    浏览(25)
  • 电力信息系统特点及安全防御

    电力信息系统的构建,为居民用电和企业服务提供了帮助,有利于促进电力行业的信息化发展。尤其是在大数据时代,对电力信息系统的运行提出了更高的要求,只有保障其安全性与可靠性,才能防止其对居民用电产生影响。网络是一个虚拟性和开放性极强的世界,在电力信

    2024年02月05日
    浏览(47)
  • 安全防御——IDS(入侵检测系统)

    IDS(intrusion detection system)入侵检测系统 是一种对网络传输进行实时监视,在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。 它与其他网络安全设备的不同之处便在于,IDS是一种积极主动的安全防护技术。 专业上讲IDS就是依照一定的安全策略,对网络、系

    2024年01月21日
    浏览(41)
  • 网络威胁防御+资产测绘系统-Golang开发

    网络威胁防御+资产测绘系统-Golang开发 项目地址:https://github.com/jumppppp/NIPS-Plus NIPS-Plus 是一款使用golang语言开发的网络威胁防御系统(内置资产测绘系统) 网络威胁流量视图 网络威胁详细信息浏览列表 网络威胁反制探测攻击IP功能 基于规则的威胁浏览检测功能 系统运行详情

    2024年02月09日
    浏览(46)
  • 网络安全产品之认识入侵防御系统

    由于网络安全威胁的不断演变和增长。随着网络技术的不断发展和普及,网络攻击的种类和数量也在不断增加,给企业和个人带来了巨大的安全风险。传统的防火墙、入侵检测防护体系等安全产品在面对这些威胁时,存在一定的局限性和不足,无法满足当前网络安全的需求。

    2024年01月22日
    浏览(41)
  • Snort开源入侵防御系统部署文档(一)

    (个人操作记录,不喜勿喷,水平低下,见谅见谅) Snort 是世界上最重要的开源入侵防御系统 (IPS)。 Snort IPS 使用一系列规则来帮助定义恶意网络活动,并使用这些规则来查找与其匹配的数据包并为用户生成警报。Snort 也可以内联部署来阻止这些数据包。 Snort 有三个主要

    2024年02月22日
    浏览(40)
  • 入侵防御系统(IPS)网络安全设备介绍

    IPS定义 IPS(Intrusion Prevention System)是一种网络安全设备或系统,用于监视、检测和阻止网络上的入侵尝试和恶意活动。它是网络安全架构中的重要组成部分,通过分析网络流量,检测入侵(包括缓冲区溢出攻击、木马、蠕虫等),并通过一定的响应方式,实时地中止入侵行为

    2024年02月08日
    浏览(41)
  • 入侵防御系统IPS,网络设计的5大原则

    互联网高速发展,使我们面临的网络安全威胁也日益严重。网络复杂度越来越高,漏洞不断涌现。黑客攻击、蠕虫病毒、木马后门、间谍软件等威胁泛滥,机密数据被盗窃,重要数据被篡改、破坏,遭受了严重的经济损失。    社交网络,在线视频,微博等,使得互联网用户

    2024年02月02日
    浏览(39)
  • 【网络安全】2.2 入侵检测和防御系统

    入侵检测和防御系统(Intrusion Detection and Prevention Systems,简称IDPS)是网络安全的重要组成部分。它们可以帮助我们发现并阻止网络攻击。在本篇文章中,我们将详细介绍IDPS的工作原理,类型,如何配置和使用IDPS,以及如何处理IDPS发现的威胁。 入侵检测和防御系统是一种设

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包