題目鏈接

第一次寫nlogn復雜度的LIS，紀念一下。

題目意思是說。有兩條平行線。兩條平行線都有n個城市，都是從左到右標記為1--n，一條線上是富有城市，一個是貧窮城市。輸入n。接下來有n行，p，r表示窮城市p和富有城市r

之間能夠建一條路（p的順序是1--n，一個貧窮城市僅僅相應一個富有城市（弱爆的語文描寫敘述能力T_T）），公路不能交叉。

問最多能夠建多少條公路。

在別處看到的對nlogn解法的解釋吧算是：

時間復雜度:(NlogN):
除了算法一的定義之外，添加一個數組b，b[i]用以表示長度為i最長子序列的最后一個數最小能夠是多少。易證：i<j時，b[i]<b[j]。

在二分查找時，一直更新b[]內容，設此時b的總長度為k，
若1. arr[i] >= b[k], 則b[k+1] = arr[i];
若2. arr[i] <?b[k], 則在b[1..k]中用二分搜索大于arr[i]的最小值。返回其位置pos，然后更新b[pos]=arr[i]。

code例如以下(自己手寫了一個二分，又用了下STL里面upper_bound，都能夠)：

//#pragma comment(linker,"/STACK:102400000,102400000") #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> //#define local using namespace std; const int maxn=500010; int poor[maxn],ro[maxn]; int n; int Binary_search(int x,int k) {int low=1,high=k;while(low<=high){int mid=(low+high)/2;if(ro[mid]<=x)low=mid+1;elsehigh=mid-1;}return low; } int lis() {int k=1;ro[k]=poor[1];for(int i=2;i<=n;i++){if(poor[i]>=ro[k])ro[++k]=poor[i];else{//int pos=Binary_search(poor[i],k);int pos=upper_bound(ro+1,ro+k+1,poor[i])-(ro);ro[pos]=poor[i];}}return k; } int main() { #ifdef localfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #endif // localint cnt=0;while(~scanf("%d",&n)){int x,y;for(int i=0;i<n;i++){scanf("%d%d",&x,&y);poor[x]=y;}int ans=lis();printf("Case %d:\n",++cnt);if(ans<=1)printf("My king, at most %d road can be built.\n\n",ans);elseprintf("My king, at most %d roads can be built.\n\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1025 Constructing Roads In JGShining#39;s Kingdom (nlogn的LIS)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。