首页 > 其他分享 >洛谷 P1020 [NOIP1999 提高组] 导弹拦截

洛谷 P1020 [NOIP1999 提高组] 导弹拦截

时间:2024-07-04 16:27:28浏览次数:26  
标签:洛谷 int res 系统 导弹 ++ P1020 NOIP1999 拦截

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行,若干个整数,中间由空格隔开。

输出格式

两行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

思路:

首先呢分析一下题目,需要我们求出系统一次最多拦多少枚,其次还需要得出一个把这些导弹全拦下的系统数量的最小值。

第一问

求一次最多拦多少枚,其实就是一个子序列问题,题目说:以后每一发炮弹都不能高于前一发的高度。那就是求最大下降子序列长度呗,这个问题如果学过"LIS"(Longest Increasing Subsequence)那基本第一问在2两分钟之内是能出代码的,没学过的话可以去了解了解,这个是在计算机科学当中是一个非常常见的概念。

第二问

求系统数量的最小值,这个确实要不好想一些。一般呢遇到这种问题尤其是这个最值他不是很直观的时候就要想:能不能贪心呢?很明显是可以的,从头遍历数组,维护的一个单调栈,如果指针指向的值小于栈顶直接加入这个栈,如果大于那就去遍历下一个栈顶,如果全部都加入不了,哎这时候就要再开一个新栈了,最后返回栈的数量就是答案啦

这里我提供两种方法:

解决

(1)动态规划

时间复杂度:O(n^2)

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
int a[N],f[N],g[N];

int n = 0,ans = 1,res = 1;

int main()
{
    while(cin >> a[n]){
        f[n] = 1;
        n ++;
    }
    for(int i=n-2;i>=0;i--){
        for(int j=n-1;j>i;j--){
            if(a[i] >= a[j]) f[i] = max(f[i],f[j] + 1);
        }
        ans = max(ans,f[i]);
    }
    cout << ans << endl;
    g[0] = a[0];
    for(int i=1;i<n;i++){
        int k = 0;
        while(k < res && g[k] < a[i]) k ++;
        g[k] = a[i];
        if(k >= res) res ++;
    }
    cout << res << endl;
    return 0;
}

   (2)二分

时间复杂度:O(nlogn)

代码
 

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int a[N], dp[N],f[N];

int main() {
    string input;
    getline(cin, input);
    stringstream ss(input);
    int n = 0;
    while (ss >> a[n]) {
        n++;
    }
    
    dp[0] = a[0];
    int cnt = 0,res = 0;
    
    for (int i = 1; i < n; i++) {
        if (a[i] <= dp[cnt]) {
            dp[++cnt] = a[i];
        } else {
            int l = 0, r = cnt;
            while (l < r) {
                int mid = (l + r) / 2;
                if (a[i] > dp[mid]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            dp[l] = a[i];
        }
    }
    cout << cnt + 1 << endl;
    f[0] = a[0];
    for(int i=1;i<n;i++){
        int k = 0;
        while(k < res && f[k] < a[i]) k ++;
        f[k] = a[i];
        if(k >= res) res ++;
    }
    cout << res << endl;
    return 0;
}

我推荐二分,二分比动态规划好,时间上面是完胜的

加油呗

标签:洛谷,int,res,系统,导弹,++,P1020,NOIP1999,拦截
From: https://blog.csdn.net/AuRoRamth/article/details/140159737

相关文章

  • 洛谷 P1011 [NOIP1998 提高组] 车站
    题目描述火车从始发站(称为第 1 站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时(即在到达第 3 站之前)车上的人数保持为 a 人。从第 3 站起(包括第 3 站)上、下车的人数有一定规律:上车的人数都是前两......
  • 洛谷2404 自然数的拆分问题 【搜索】
    自然数的拆分问题题目描述任何一个大于111的自然数nnn,总可以拆......
  • 洛谷 P5723 【深基4.例13】质数口袋 题解
    题面传送门观察题目,我们可以看到这是一道朴素的,判断质数的一道题目。何为质数?质数就是除了111和这个本身,没有其他因数的数。特别的,......
  • C++题解(1) 信息学奥赛一本通 1003:对齐输出 洛谷 B2004:对齐输出 土豆编程 T1003:对
    【题目描述】读入三个整数,按每个整数占8个字符的宽度,右对齐输出它们,按照格式要求依次输出三个整数,之间以一个空格分开。【输入】只有一行,包含三个整数,整数之间以一个空格分开。【输出】只有一行,按照格式要求依次输出三个整数,之间以一个空格分开。【输入样例】......
  • 洛谷 U285997 松鼠没有家
    https://www.luogu.com.cn/problem/U285997#submit题目描述星斗大森林里有一棵参天巨树,树上有 nn 个结点,我们给它们编号 11~nn。松鼠每天从树的这头窜到那头,因为它不认真写信息学作业只想划树叶子(树上没办法划水啊),被妈妈给批评了,于是回不了家。现在松鼠想要知道,它从......
  • 洛谷 P1030 [NOIP2001 普及组] 求先序排列
    因为题目求先序,意味着要不断找根。那么我们来看这道题方法:(示例)中序ACGDBHZKX,后序CDGAHXKZB,首先可找到主根B;那么我们找到中序遍历中的B,由这种遍历的性质,可将中序遍历分为ACGD和HZKX两棵子树,那么对应可找到后序遍历CDGA和HXKZ(从头找即可)从而问题就变成求1.中序遍历ACGD,后序......
  • 洛谷
    题目链接:思路    代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e4+10;llx,y,dx,dy,n;boolvis[N];intmp[1010][1010];structpoint{intx,y;booloperator<(conststructpointa)const{......
  • 洛谷P1304 哥德巴赫猜想 (质数题) (内含埃氏筛和欧拉筛等一些小总结解释)
    题目题目解析题目意思很简单,对于每一组数据来说,就是找这个偶数的两个质数相加的那两个质数,并且要满足加法中的第一个质数要是最小的质数,满足第一个质数是最小的质数的情况下也要保证第二个数也是质数代码#include<bits/stdc++.h>usingnamespacestd;boolis_prime(in......
  • 洛谷 P1020 导弹拦截
    题目链接:导弹拦截思路    代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inta[N],x,l,dp[N],maxn;intg[N],cnt;intmain(){while(cin>>x)a[++l]=x;for(inti=1;i<=l;i++){intk=1......
  • P1255洛谷
    #include<bits/stdc++.h>#include<math.h>#include<cmath>usingnamespacestd;constintmaxn=5050;structBigInt{  inta[maxn];  intlen;  BigInt(){len=1;memset(a,0,sizeofa);}  BigInt(char*s){    len=strlen(s);  ......