P1020-导弹拦截

 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
",dp1sum);
48     printf("%d
",dp2sum);
49     return 0;
50 }