1260：【例9.4】拦截导弹(Noip1999)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll N=1e3+520,INF=0x3f3f3f3f;
 5 ll dp[N],dp2[N],k[N],cnt,n,maxn;
 6 int main()
 7 {
 8     ll len=0;
 9     dp[0]=-INF,dp2[0]=-INF;
10     while(~scanf("%lld",&n))
11     {
12         ll l=0,r=len;
13         while(l<r)
14         {   
15             ll mid=l+r+1>>1;
16             if(dp[mid]>=n) l=mid;//在什么序列查找什么,最后l，r是相等的 
17             else r=mid-1; 
18         }
19         len=max(len,r+1); 
20         dp[r+1]=n;
21         l=0,r=cnt;
22         while(l<r)
23         {
24             ll mid=l+r>>1;
25             if(dp2[mid]>=n) r=mid;     
26             else l=mid+1; 
27         }
28         if(dp2[r]<n) r++;
29         cnt=max(cnt,r);
30         dp2[r]=n; 
31     } 
32     cout<<len<<‘\n‘<<cnt<<‘\n‘;
33     return 0;
34 }