hdu 1025 Constructing Roads In JGShining's Kingdom

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1025

参考博客：http://www.felix021.com/blog/read.php?1587

最长不下降子序列，有一种DP+二分的求法

最长递增子序列 O(NlogN)算法

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int a[500001],d[500001];
 4 int find(int a,int left,int rig)
 5 {
 6     int mid;
 7     while(left<=rig)
 8     {
 9         mid=(left+rig)/2;
10         if(a>d[mid])   left=mid+1;
11         else rig=mid-1;
12     }
13     return left;
14 };
15 
16 int main()
17 {
18     int i,n,p,k,t,x=1,len;
19     while(~scanf("%d",&n))
20     {
21         for(i=1; i<=n; i++)
22         {
23             scanf("%d%d",&p,&k);
24             a[p]=k;
25         }
26         d[1]=a[1];
27         len=1;
28         for(i=2; i<=n; i++)
29         {
30             t=find(a[i],1,len);
31             d[t]=a[i];
32 
33             if(t>len)
34             len++;
35         }
36         if(len==1)
37         printf("Case %d:\nMy king, at most %d road can be built.\n\n",x,len);
38         else
39         printf("Case %d:\nMy king, at most %d roads can be built.\n\n",x,len);
40         x++;
41         memset(a,0,sizeof(a));
42         memset(d,0,sizeof(d));
43     }
44 }

话说，这题我没看出来O(NlogN)，感觉课本上的求最长上升子序列也不是N*N,不过这题用上面的代码过了，耗时稍微有点多。