hdu1025Constructing Roads In JGShining's Kingdom(巧求最长子序列）
最长上升子序列的时间复杂度为O(n2)，此处为500000，上网看了看别人的解题报告，才知道它有两种算法复杂度为O(n*logn)和O(n^2)。前者使用二分查找，后者朴素查找。它的算法大致思路：设置两个a,b数组，a数组存储数据，b数组存储最长不降序序列。此算法关键在于设计二分查找。二分查找关键代码来自http://blog.****.net/ice_crazy/article/details/7536332
1 #include<stdio.h> 2 int a[500011],dp[500011]; 3 int main() 4 { 5 int n,temp1,temp2,i,k; 6 k=0; 7 while(scanf("%d",&n)!=-1) 8 { 9 for(i=1;i<=n;i++) 10 { 11 scanf("%d%d",&temp1,&temp2); 12 a[temp1]=temp2; 13 } 14 dp[1]=a[1]; 15 int low,len,high,mid; 16 len=1; 17 for(i=2;i<=n;i++) 18 { 19 low=1; 20 high=len; 21 while(low<=high) 22 { 23 mid=(low+high)/2; 24 if(dp[mid]<a[i]) 25 low=mid+1; 26 else 27 high=mid-1; 28 } 29 dp[low]=a[i]; 30 if(low>len) 31 len++; 32 } 33 k++; 34 printf("Case %d: ",k); 35 if(len==1) printf("My king, at most 1 road can be built. "); 36 else 37 printf("My king, at most %d roads can be built. ",len); 38 printf(" "); 39 } 40 return 0; 41 } 42 43