https://www.luogu.org/problemnew/show/P1020 （原題鏈接） 第一問就是求最長不上升子序列的長度，自然就想到了c++一本通里動態規劃里O（n^2）的演算法，但題目明確說明“為了讓大家更好地測試n方演算法，本題開啟spj，n方100分，nlogn200分每點兩問，按 ...
https://www.luogu.org/problemnew/show/P1020
（原題鏈接）
第一問就是求最長不上升子序列的長度，自然就想到了c++一本通里動態規劃里O（n^2）的演算法，但題目明確說明“為了讓大家更好地測試n方演算法，本題開啟spj，n方100分，nlogn200分每點兩問，按問給分”，自然是要寫O(nlogn)的演算法才能AC哦。
對於這種nlogn的演算法，只能求出長度，不能求出具體的序列。這種演算法實現過程如下：
我們定義len為到目前為止最長不上升子序列的長度，d[l]表示此長度為l的不上升子序列的末尾數據中最下的那個，a[i]為輸入的第i個結果。先使d[1]=1，len=1。我們從i=2(i<=n)開始看：
如果a[i]<=d[len]，那麼使d[++len]=a[i]，即擴充一下目前的最長不上升子序列；
否則，a[i]>d[len]，就在數組d中從前往後找到第一個<a[i]的元素d[j]，此時d[i1,2,...,j-1]都>=a[i]，那麼它完全可以接上d[j-1]然後生成一個長度為j的不上升子序列，而且這個子序列比當前的d[j]這個子序列更有潛力（因為這個數比d[j]大），所以就替換掉它就行了。
至於第一個大於它的怎麼找……STL中的 upper_bound（x,x+n,num,greater<int>()），每次複雜度logn,在不嚴格單調增加的int型x數組從頭找到下標n-1,若找到第一個比num小的數，則返回它的地址，否則返回下標為n的數的地址（地址-數組名=數的下標）。別忘了頭文件為<algorithm>。更多用法詳見https://blog.csdn.net/qq_40160605/article/details/80150252
第二問可由Dilworth定理（大致意思是一個數列分成不上升（或不下降）子序列的最小數=該數列的最長上升（或下降）子序列的長度）知該問是求最長上升子序列
的長度。具體實現過程與第一問類似只是將第一問實現過程中加粗的4個不等號分別改成“>,<=,>,<=”就行了，思路與第一問一模一樣。
終於上代碼了：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int a[100001],d[100001]; 6 int n; 7 void bss(); 8 void ss(); 9 int main() 10 { 11 char ch=' '; 12 while(ch==' ') 13 { 14 scanf("%d",&a[++n]); 15 ch=getchar(); 16 } 17 bss();//求最大不上升序列長度的函數 18 ss();//求最大上升序列的長度的函數 19 return 0; 20 } 21 void bss() 22 { 23 int len=1; 24 d[len]=a[1]; 25 for(int i=2;i<=n;++i) 26 { 27 if(a[i]<=d[len]) 28 { 29 d[++len]=a[i]; 30 } 31 else 32 { 33 d[upper_bound(d+1,d+len+1,a[i],greater<int>())-d]=a[i]; 34 } 35 } 36 cout<<len<<endl; 37 } 38 void ss() 39 { 40 int len=1; 41 d[len]=a[1]; 42 for(int i=2;i<=n;++i) 43 { 44 if(a[i]>d[len]) 45 { 46 d[++len]=a[i]; 47 } 48 else 49 { 50 if(a[i]!=d[len]) 51 { 52 d[lower_bound(d+1,d+len+1,a[i])-d]=a[i]; 53 } 54 } 55 } 56 cout<<len; 57 }//代碼已AC
加油吧！
2019.2
