https://www.51nod.com/tutorial/course.html#!courseId=12
解題關鍵：
如果將子序列按照長度由短到長排列，將他們的最大元素放在一起，形成新序列$B\left\{ {{b_1},{b_2}, \ldots ?\ldots ,{b_j}} \right\}$，則序列$B$滿足${b_1} < {b_2} < ?\ldots ?\ldots ?< {b_j}$。這個關系比較容易說明，假設${b_{xy}}$表示序列A中長度為$x$的遞增序列中的第$y$個元素，顯然，如果在序列$B$中存在元素${b_{mm}} > {b_{nn}}$，且$m < n$則說明子序列${B_n}$的最大元素小于${B_m}$的最大元素，因為序列是嚴格遞增的，所以在遞增序列${B_n}$中存在元素${b_{nm}} < {b_{nn}}$，且從${b_{n0}}$到${b_{nm}}$形成了一個新的長度為$m$的遞增序列，因為${b_{mm}} > {b_{nn}}$，所以${b_{mm}} > {b_{nm}}$，這就說明在序列$B$中還存在一個長度為$m$，最大元素為${b_{nm}} < {b_{mm}}$的遞增子序列，這與序列的定義，${b_{mm}}$是所有長度為m的遞增序列中第$m$個元素最小的序列不符，所以序列$B$中的各元素嚴格遞增。
?
注意liss存的是下標，主要是為了求pre用，若只求max，你當然可以設成值。?
爆炸了，剛發現《挑戰競賽程序設計》上有一個代碼非常非常簡短的模板，炸了；
STL模板：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<functional> 6 using namespace std; 7 8 const int N=131072; 9 int n=7, a[N] = {0,0,1,1,0,0,2}; 10 template<class Cmp> 11 int LIS (Cmp cmp){ 12 static int m=0,end[N]; 13 for(int i=0;i<n;i++){ 14 int pos=lower_bound(end,end+m,a[i],cmp)-end; 15 end[pos]=a[i],m+=pos==m; 16 } 17 return m; 18 } 19 bool greater1(int value){ 20 return value>=1; 21 } 22 23 int main(){ 24 cout<<LIS(less<int>())<<endl; //嚴格上升 25 cout<<LIS(less_equal<int>())<<endl; //非嚴格上升 26 cout<<LIS(greater<int>())<<endl; //嚴格下降 27 cout<<LIS(greater_equal<int>())<<endl;//非嚴格下降 28 cout<<count_if(a,a+7,greater1)<<endl; //計數 29 //第二個參數為末尾元素的下一個位置 30 return 0; 31 }
?
最終模板：
1 #include<bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 using namespace std; 4 typedef long long ll; 5 ll a[50002],dp[50002]; 6 int main(){ 7 int n; 8 cin>>n; 9 for(int i=0;i<n;i++){ 10 cin>>a[i]; 11 } 12 fill(dp,dp+n,INF); 13 for(ll i=0;i<n;i++){ 14 *lower_bound(dp,dp+n,a[i])=a[i]; 15 } 16 printf("%lld\n",lower_bound(dp,dp+n,INF)-dp); 17 }
?
自己改進模板（不帶路徑）：注意二分時上界為len+1就ok了，也可以fill成inf，更簡單明了
1 #include<bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 using namespace std; 4 typedef long long ll; 5 int arr[50002],dp[50002]; 6 int n,len; 7 int find1(int x){ 8 int mid,l=1,r=len+1; 9 while(l<r){ 10 mid=(l+r)>>1; 11 if(dp[mid]>x) r=mid; 12 else l=mid+1; 13 } 14 return r; 15 } 16 int lis(){ 17 int dex; 18 for(int i=1;i<=n;i++){ 19 dex=find1(arr[i]); 20 dp[dex]=arr[i]; 21 len=max(len,dex); 22 } 23 return len; 24 } 25 int main(){ 26 cin>>n; 27 for(int i=1;i<=n;i++){ 28 cin>>arr[i]; 29 } 30 ll ans=lis(); 31 printf("%lld\n",ans); 32 return 0; 33 }
?
?
?
?帶路徑模板1
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 int a[50002],dp[50002],pre[50002],res[50002],n; 9 int len; 10 11 int find1(int x){ 12 int mid,l=1,r=len+1; 13 while(l<r){ 14 mid=(l+r)>>1; 15 if(a[dp[mid]]>x) r=mid; 16 else l=mid+1; 17 } 18 return r; 19 } 20 21 int lis(){ 22 len=0; 23 for(int i=1;i<=n;i++){ 24 int dex=find1(a[i]); 25 dp[dex]=i; 26 if(dex!=1) pre[i]=dp[dex-1]; 27 len=max(len,dex); 28 } 29 30 int k=dp[len],t=len; 31 while(pre[k]!=k){ 32 res[t--]=a[k]; 33 k=pre[k]; 34 } 35 res[t]=a[k]; 36 return len; 37 } 38 int main(){ 39 cin>>n; 40 for(int i=0;i<=n+2;i++) pre[i]=i; 41 for(int i=1;i<=n;i++) cin>>a[i]; 42 43 ll ans=lis(); 44 printf("%lld\n",ans); 45 for(int i=1;i<=ans;i++){ 46 printf("%d ",res[i]); 47 } 48 printf("\n"); 49 }
?
?帶路徑模板2
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 int arr[50002],liss[50002],pre[50002],res[50002]; 9 int find1(int i,int l,int r){ 10 int mid; 11 while(l<r){ 12 mid=(l+r)>>1; 13 if(arr[liss[mid]]>arr[i]) r=mid; 14 else l=mid+1; 15 } 16 return r; 17 } 18 int lis(int len){ 19 int max=1; 20 liss[0]=0; 21 for(int i=0;i<len;i++){ 22 int index=find1(i,0, max-1); 23 if(index==0&&arr[liss[index]]>=arr[i]){ 24 liss[index]=i; 25 continue; 26 }//增加這條語句主要是pre的影響，不需要路徑的話，完全可以去掉。 27 if(index==max-1&&arr[liss[index]]<arr[i]){ 28 liss[max++]=i; 29 pre[i]=liss[index]; 30 continue; 31 } 32 liss[index]=i; 33 pre[i]=liss[index-1]; 34 } 35 36 int k=liss[max-1],t=max-1; 37 while(pre[k]!=k){ 38 res[t--]=arr[k]; 39 k=pre[k]; 40 } 41 res[t]=arr[k]; 42 return max; 43 } 44 int main(){ 45 int n; 46 cin>>n; 47 for(int i=0;i<n+2;i++){ 48 pre[i]=i; 49 } 50 for(int i=0;i<n;i++){ 51 cin>>arr[i]; 52 } 53 ll ans=lis(n); 54 printf("%lld\n",ans); 55 for(int i=0;i<ans;i++){ 56 printf("%d ",res[i]); 57 } 58 printf("\n"); 59 }
?
)
】...)
