导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是

输入格式

输出格式

输入输出样例

输入 #1

389 207 155 300 299 170 158 65

输出 #1

6
2

说明/提示

为了让大家更好地测试n方算法，本题开启spj，n方100分，nlogn200分

每点两问，按问给分

分析：

超级经典的一道题，考了最长不上升子序列和最长上升子序列，不知道为什么我到现在才做（划掉），而且突然N LOG N的算法我前几篇LIS的题目好像都写错了emmmm。。。

CODE :

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 const int M=100005;
 8 int a[M],n,lena,lenb;
 9 int d1[M],d2[M];
10 int get(){
11     int res=0,f=1;
12     char c=getchar();
13     while (c>'9'||c<'0') {
14         if (c=='-') f=-1;
15         c=getchar();
16     }
17     while (c<='9'&&c>='0'){
18         res=(res<<3)+(res<<1)+c-'0';
19         c=getchar();
20     }
21     return res*f;
22 }
23 int main(){
24     freopen("a.in","r",stdin);
25     freopen("a.out","w",stdout);
26     while (cin>>a[++n]);
27     n--;
28     d1[++lena]=a[1];
29     d2[++lenb]=a[1];
30     for (int i=2;i<=n;i++){
31         if (d1[lena]>=a[i]) d1[++lena]=a[i];
32         else{
33             int j=upper_bound(d1+1,d1+lena+1,a[i],greater<int>())-d1;
34             d1[j]=a[i]; 
35          }
36          if (d2[lenb]<a[i]) d2[++lenb]=a[i];
37          else {
38              int j=lower_bound(d2+1,d2+lenb+1,a[i])-d2;
39             d2[j]=a[i];
40          }
41     }
42     //for (int i=1;i<=lena;i++) cout<<d1[i]<<endl;
43     printf ("%d
%d
",lena,lenb);
44     return 0;
45 }