首页 > 代码库 > hdu--1025--LIS
hdu--1025--LIS
这题的考察点 应该有2个
一个是对于LIS算法的优化 使用进行二分查找的O(nlogn)算法 而不是 O(n^2)
另一个就是 对于题意的理解... 并不是可以很直观地联系到 最长上升子序列的...
你可以自己画图 就很直观了..
touch me
另外一个很坑的地方 就是 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 else22 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:\n",cnt++ );47 if( maxLen>1 )48 printf( "My king, at most %d roads can be built.\n\n",maxLen );49 else50 printf( "My king, at most %d road can be built.\n\n",maxLen );51 }52 return 0;53 }
这里 我用cin cout的时候就tle了.... 虽然使用了cin.sync_with_stdio(false); 很无语=-=