P1020-导弹拦截

ゞ浴缸里的玫瑰 2023-06-01 08:51 50阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 typedef long long ll;
     4 using namespace std;
     5 inline bool read(int &x)
     6 {
     7     char c=getchar();
     8     if(c==EOF)return false;
     9     while(c>'9'||c<'0')c=getchar();
    10     while(c>='0'&&c<='9')
    11     {
    12         x=(x<<1)+(x<<3)+(c^48);
    13         c=getchar();
    14     }
    15     return true;
    16 }
    17 
    18 int a[100003];
    19 int dp1[100003];
    20 int dp1sum = 1;
    21 int dp2[100003];
    22 int dp2sum = 1;
    23 int n = 0;
    24 int main()
    25 {
    26     memset(a,0,sizeof(a));
    27     while(read(a[n++]));n--;
    28     
    29     dp2[1] = dp1[1] = a[0];
    30     _for(i,1,n)
    31     {
    32         if(a[i]<=dp1[dp1sum])
    33             dp1[++dp1sum] = a[i];    
    34         else
    35         {
    36             int k = upper_bound(dp1+1,dp1+dp1sum+1,a[i],greater<int>())-dp1;
    37             dp1[k] = a[i];
    38         }
    39         if(a[i]>dp2[dp2sum])
    40             dp2[++dp2sum] = a[i];
    41         else
    42         {
    43             int k = lower_bound(dp2+1,dp2+dp2sum+1,a[i])-dp2;
    44             dp2[k] = a[i];
    45         }
    46     }
    47     printf("%d\n",dp1sum);
    48     printf("%d\n",dp2sum);
    49     return 0;
    50 }

转载于:https://www.cnblogs.com/Asurudo/p/11319423.html

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1020-导弹拦截

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

ゞ浴缸里的玫瑰/ 2023年06月01日 08:51/ 0 赞/ 51 阅读

相关拦截导弹（经典dp）

拦截导弹时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系

左手的ㄟ右手/ 2022年09月30日 06:51/ 0 赞/ 278 阅读

相关 1008 拦截导弹2

Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都

谁践踏了优雅/ 2022年09月11日 12:25/ 0 赞/ 200 阅读

相关 NYOJ 79 拦截导弹

拦截导弹时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有

刺骨的言语ヽ痛彻心扉/ 2022年08月25日 05:22/ 0 赞/ 238 阅读

相关又见拦截导弹

又见拦截导弹时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述大家对拦截导弹那个题目应该比较熟悉了，我再叙述一下题意：某国为了防

水深无声/ 2022年08月05日 07:26/ 0 赞/ 248 阅读

相关算法：拦截导弹

题目描述：某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前

逃离我推掉我的手/ 2022年06月10日 11:22/ 0 赞/ 257 阅读

相关 nyoj--79--拦截导弹

拦截导弹时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系

青旅半醒/ 2022年06月10日 06:45/ 0 赞/ 258 阅读

相关洛谷 P1020 导弹拦截

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高

阳光穿透心脏的1/2处/ 2022年05月28日 12:15/ 0 赞/ 229 阅读

相关 P1020 导弹拦截

题目描述：题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能

我就是我/ 2022年02月25日 09:14/ 0 赞/ 321 阅读

相关洛谷 P1020导弹拦截题解

洛谷链接：[https://www.luogu.org/problem/P1020][https_www.luogu.org_problem_P1020] 题目描述某

我就是我/ 2021年10月29日 18:44/ 0 赞/ 537 阅读