#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<functional> using namespace std; const int N = 131072;int a[N]; int LIS_regular (int n) //嚴格上升 {int len=0;int d[N];d[len]=a[0];for (int i=1;i<n;i++){if (a[i]>d[len])d[++len]=a[i];else{int pos=lower_bound (d,d+len+1,a[i],less<int>() )-d;d[pos]=a[i];}} return len+1; } int LIS_irregular (int n) //非嚴格上升 {int len=0;int d[N];d[len]=a[0];for (int i=1;i<n;i++){if (a[i]>=d[len])d[++len]=a[i];else{int pos=lower_bound (d,d+len+1,a[i],less_equal<int>() )-d;d[pos]=a[i];}} return len+1; } int LDS_regular (int n) //嚴格下降 {int len=0;int d[N];d[len]=a[0];for (int i=1;i<n;i++){if (a[i]<d[len])d[++len]=a[i];else{int pos=lower_bound (d,d+len+1,a[i],greater<int>())-d;d[pos]=a[i];}} return len+1; } int LDS_irregular (int n) //非嚴格下降 {int len=0;int d[N];d[len]=a[0];for (int i=1;i<n;i++){if (a[i]<=d[len])d[++len]=a[i];else{int pos=lower_bound (d,d+len+1,a[i],greater_equal<int>())-d;d[pos]=a[i];}} return len+1; } int main () {int n;scanf ("%d",&n);for (int i=0;i<n;i++)scanf ("%d",&a[i]);printf ("最長嚴格上升子序列長度: %d \n",LIS_regular(n));printf ("最長不嚴格上升子序列長度: %d \n",LIS_irregular(n));printf ("最長嚴格下降子序列長度: %d \n",LDS_regular(n));printf ("最長不嚴格下降子序列長度: %d \n",LDS_irregular(n));return 0; }

?

總結

以上是生活随笔為你收集整理的LIS、LDS模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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