这题的考察点 应该有2个
一个是对于LIS算法的优化 使用进行二分查找的O(nlogn)算法 而不是 O(n^2)
另一个就是 对于题意的理解... 并不是可以很直观地联系到 最长上升子序列的...
你可以自己画图 就很直观了..
另外一个很坑的地方 就是 road || roads 太无语了
这题 在discuess里 有人提了一个很创新的方法 树状数组---我先自己去琢磨下再说~
对于LIS 网上有很多篇介绍 但给我感觉那百度到的第一篇 讲了很多没用的话.....
O(n^2) 就是 一个状态转移方程 dp[X] = max( dp[X],dp[X-1]+1)完事了 然后因为你既然都要接触LIS了 肯定也是有一定基础了 当然都可以自己写出来~
O(nlogn)的二分思想 很真的是不错的 反正 对于大数据 一般不用这个方法肯定是TLE的...
使用O(nlongn) 你只要理解这2点（直接搬运他们写的了) -->A数组就是待查找的数组 F[X]数组就是当前最长长度为X时末尾的值-->这个值我们尽量往小了取 这样就可以取得更长的长度 原因见下面:
假设有两个元素A[x]和A[y]，满足
(1)x < y < t
(2)A[x] < A[y] < A[t]
(3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到同样的F[t]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？
很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[t-1]这一段中如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 int n , maxLen , cnt = 1; 5 const int size = 500010; 6 int arr[size]; 7 int dp[size]; 8 9 int bSearch( int val , int len ) 10 { 11 int l , r , mid; 12 l = 1; 13 r = len; 14 while( l<=r ) 15 { 16 mid = l + (r-l)/2; 17 if( val==dp[mid] ) 18 return mid; 19 else if( val>dp[mid] ) 20 l = mid + 1; 21 else 22 r = mid - 1; 23 } 24 return l; 25 } 26 27 int main() 28 { 29 int x, y , temp; 30 while( ~scanf("%d",&n) ) 31 { 32 maxLen = 1; 33 for( int i = 1 ; i<=n ; i++ ) 34 { 35 scanf( "%d %d",&x,&y ); 36 arr[x] = y; 37 } 38 dp[1] = arr[1]; 39 for( int i = 2 ; i<=n ; i++ ) 40 { 41 temp = bSearch( arr[i] , maxLen ); 42 dp[temp] = arr[i]; 43 if( temp>maxLen ) 44 maxLen++; 45 } 46 printf( "Case %d: ",cnt++ ); 47 if( maxLen>1 ) 48 printf( "My king, at most %d roads can be built. ",maxLen ); 49 else 50 printf( "My king, at most %d road can be built. ",maxLen ); 51 } 52 return 0; 53 }
这里 我用cin cout的时候就tle了.... 虽然使用了cin.sync_with_stdio(false); 很无语=-=