最长不下降子序列及二分优化

    xiaoxiao2025-04-21  8

    最长不下降子序列是动态规划的必做入门题

    普通做法如下:

    #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int a[1001][3]; //a[i][1]用来记录输入的值,a[i][2]用来记录从最后一个到编号为i的数最长不下降子序列的长度,a[i][3]用来记录上一个数,便于打印; int main(){ int i,j,k,m,n; cin>>m; for(i=1;i<=m;i++){ cin>>a[i][1]; a[i][2]=1;//初始化长度为1,包括他本身; a[i][3]=0; //0为没有数 } for(i=m-1;i>=1;i--){ k=0;//k记录从后往前枚举到i最长长度; n=0;//n记录上一个数的编号; for(j=i+1;j<=m;j++){ if((a[i][1]<a[j][1])&&(a[j][2]>k)){//若当前值比上一个值小且比当前最长长度小; k=a[j][2];//更新 n=j;//记录 } } if(k>0){ a[i][2]=k+1;//加上当前值的长度1 a[i][3]=n; } } n=1;//从后往前搜索看长度最长的是多少 for(j=2;j<=m;j++){ if(a[j][2]>a[n][2])n=j; } cout<<a[n][2]<<endl; return 0; } 若要打印序列,则还要加上如下几行代码:

    while(n!=0){ cout<<a[n][1]<<' '; n=a[n][3]; }接下来介绍O(n)的二分算法

    这个算法的弊端是只能算出不下降子序列的长度而不能打印序列

    这个算法思想就是把输入的数放入一个栈里,

    从第一个数开始,一个一个和后面的比较;

    若后面的数比栈内队尾的数大,添加此元素进栈,队尾加一

    若位于中间位置,则把栈内刚好比他大的数删除,并添加至此元素被删的位置,因为在序列长度不会变长的情况下,小的数更有前途

    记住比较时是二分比较

    最后输出栈长即可

    #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[100010],b[100010],top; int dp(int j){ int f=0,l=top; while(f<l){ int mid=(f+l)/2; if(b[mid]>a[j])l=mid; else f=mid+1; } return f; } int main(){ int i,j,k,m,n,p; scanf("%d",&p); for(k=1;k<=p;k++){ top=0; memset(b,0,sizeof(b)); memset(a,0,sizeof(a)); scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d",&a[i]); b[++top]=a[1]; for(j=2;j<=m;j++){ if(a[j]>b[top])b[++top]=a[j]; else{ n=dp(j); b[n]=a[j]; } } printf("%d\n",top); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-1298312.html
    最新回复(0)