首页 > 其他 > 详细

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

时间:2021-08-02 14:45:23      阅读:25      评论:0      收藏:0      [点我收藏+]

http://ybt.ssoier.cn:8088/problem_show.php?pid=1260

 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 }

 

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

原文:https://www.cnblogs.com/Astronaut0142/p/15089051.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!