[dp]最长单调递增子序列LIS

/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){ 12static int m=0,end[N];13for(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} 17return m;18 } 19 bool greater1(int value){ 20return value>=1; 21 } 22 23 int main(){24cout<<LIS(less<int>())<<endl; //严格上升 25cout<<LIS(less_equal<int>())<<endl; //非严格上升 26cout<<LIS(greater<int>())<<endl;//严格下降 27cout<<LIS(greater_equal<int>())<<endl;//非严格下降 28cout<<count_if(a,a+7,greater1)<<endl; //计数 29//第二个参数为末尾元素的下一个位置 30return 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(){ 7int n; 8cin>>n; 9for(int i=0;i<n;i++){10 cin>>a[i];11}12fill(dp,dp+n,INF);13for(ll i=0;i<n;i++){14 *lower_bound(dp,dp+n,a[i])=a[i];15}16printf("%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){ 8int mid,l=1,r=len+1; 9while(l<r){10 mid=(l+r)>>1;11 if(dp[mid]>x) r=mid;12 else l=mid+1;13}14return r;15 }16 int lis(){17int dex;18for(int i=1;i<=n;i++){19 dex=find1(arr[i]);20 dp[dex]=arr[i];21 len=max(len,dex);22}23return len;24 }25 int main(){26cin>>n;27for(int i=1;i<=n;i++){28 cin>>arr[i];29}30ll ans=lis();31printf("%lld\n",ans);32return 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){12int mid,l=1,r=len+1;13while(l<r){14 mid=(l+r)>>1;15 if(a[dp[mid]]>x) r=mid;16 else l=mid+1;17}18return r;19 }20 21 int lis(){22len=0;23for(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}2930int k=dp[len],t=len;31while(pre[k]!=k){32 res[t--]=a[k];33 k=pre[k];34}35res[t]=a[k];36return len;37 }38 int main(){39cin>>n;40for(int i=0;i<=n+2;i++) pre[i]=i;41for(int i=1;i<=n;i++) cin>>a[i];4243ll ans=lis();44printf("%lld\n",ans);45for(int i=1;i<=ans;i++){46 printf("%d ",res[i]);47}48printf("\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){10int mid;11while(l<r){12 mid=(l+r)>>1;13 if(arr[liss[mid]]>arr[i]) r=mid;14 else l=mid+1;15}16return r;17 }18 int lis(int len){19int max=1;20liss[0]=0;21for(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}3536int k=liss[max-1],t=max-1;37while(pre[k]!=k){38 res[t--]=arr[k];39 k=pre[k];40}41res[t]=arr[k];42return max;43 }44 int main(){45int n;46cin>>n;47for(int i=0;i<n+2;i++){48 pre[i]=i;49}50for(int i=0;i<n;i++){51 cin>>arr[i];52}53ll ans=lis(n);54printf("%lld\n",ans);55for(int i=0;i<ans;i++){56 printf("%d ",res[i]);57}58printf("\n");59 }