2 最长上升子序列及其衍生_最长上升子序列变种

目录

最长上升子序列模板

1 怪盗基德的滑翔翼

2 登山

3 合唱队形

4 友好城市 （贪心）

5 最长上升子序列和

6 拦截导弹 （贪心）

7 导弹防御系统 （贪心+dfs）

8  最长公共上升子序列 （最长公共子序列+最长上升子序列）

1）朴素版（容易TLE）

2) 分析优化一维

3) 滚动数组优化二维数组变成一维

---

最长上升子序列模板

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N],a[N];
int main()
{
   int n,ans=0;
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//表示只有自己一个数的时候
        for(int j=1;j<i;j++)
            if(a[j]<a[i])//假如这个位置上的数比我小
                f[i]=max(f[i],f[j]+1);//则进行状态转移
        ans=max(ans,f[i]);//更新一下以每个数结尾的最长上升子序列的最大值
    }
    cout<<ans<<endl;
    return 0;
}

1 怪盗基德的滑翔翼

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

//因为是从一个点可以飞两个方向，故求正向求一次最长上升子序列，逆向也求一次，最后取最大值
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int h[N],f[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>h[i];
        //正向求一次最长上升子序列
        for(int i=1;i<=n;i++)
        {
            f[i]=1;
            for(int j=1;j<i;j++)
                if(h[j]<h[i])
                  f[i]=max(f[i],f[j]+1);
            ans=max(f[i],ans);//更新最大值
        }
        //逆向求一次最畅销上升子序列
        for(int i=n;i;i--)
        {
            f[i]=1;
            for(int j=n;j>i;j--)
                if(h[j]<h[i])
                  f[i]=max(f[i],f[j]+1);
            ans=max(f[i],ans);//更新最大值
        }
        cout<<ans<<endl;
    }
    return 0;
}

2 登山

​​​​​​信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int h[N],f[N];//f存的是以i结尾的最长上升子序列
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    //正向求一次最长上升子序列
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(h[j]<h[i])
                f[i]=max(f[i],f[j]+1);
    }
    //逆向求一次最长上升子序列
    for(int i=n;i;i--)
    {
        int flag=f[i];//先把正向的最长上升子序列记录下来
        f[i]=1;//在从新求逆向的最长上升子序列
        for(int j=n;j>i;j--)
            if(h[j]<h[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(f[i]+flag-1,ans);//更新一下两个和的最大值，因为第i这个数被加了两次1,故结果得减一
    }
    cout<<ans<<endl;
    return 0;
}

3 合唱队形

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

题意跟登山一模一样，只是结果要的是去掉的人

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int h[N],f[N];//f存的是以i结尾的最长上升子序列
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    //正向求一次最长上升子序列
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(h[j]<h[i])
                f[i]=max(f[i],f[j]+1);
    }
    //逆向求一次最长上升子序列
    for(int i=n;i;i--)
    {
        int flag=f[i];//先把正向的最长上升子序列记录下来
        f[i]=1;//在从新求逆向的最长上升子序列
        for(int j=n;j>i;j--)
            if(h[j]<h[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(f[i]+flag-1,ans);//更新一下两个和的最大值，因为第i这个数被加了两次1,故结果得减一
    }
    cout<<n-ans<<endl;//结果要去掉的人
    return 0;
}

4 友好城市 （贪心）

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=5010;
int f[N];
pii he[N];//存两边对应的友好城市
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        he[i]={a,b};
    }
    sort(he+1,he+n+1);//按北岸的城市排序
    //求一下南岸的最长上升子序列
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(he[j].second<he[i].second)
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;//输出南岸的最长上升子序列，也就是最大不相交数
    return 0;
}

5 最长上升子序列和

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e3+10;
int f[N],a[N];
int main()
{
   int n,ans=0;
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=a[i];//空的时候，只有自己
        for(int j=1;j<i;j++)
            if(a[j]<a[i])//假如这个数小于当前数
                f[i]=max(f[i],f[j]+a[i]);//进行状态转移
        ans=max(ans,f[i]);//更新一下最大值
    }
    cout<<ans<<endl;
    return 0;
}

 

6 拦截导弹 （贪心）

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N],q[N],f[N];
int main()
{
   int n=0;
   while(cin>>a[n]) n++;
   int ans=0;
   //求最长上升子序列
   for(int i=0;i<n;i++)
   {
       f[i]=1;
       for(int j=0;j<i;j++)
        if(a[j]>=a[i])
          f[i]=max(f[i],f[j]+1);
       ans=max(f[i],ans);
   }
   cout<<ans<<endl;
   //求覆盖次数，贪心
   int cnt=0;
   for(int i=0;i<n;i++)
   {
      int k=0;
      while(k<cnt&&q[k]<a[i]) k++;//找现有序列中大于当前数的最小的数
      q[k]=a[i];//更新一下当前数
      if(k>=cnt) cnt++;//否则开辟新的子序列
   }
   cout<<cnt;
    return 0;
}

 

7 导弹防御系统 （贪心+dfs）

 

187. 导弹防御系统 - AcWing题库

跟拦截导弹的贪心一样，多了dfs

#include<bits/stdc++.h>
using namespace std;
const int N=60;
int a[N],up[N],down[N];
int ans=0,n;
void dfs(int u,int su,int sd)//u表示当前数，su表示上升子序列的数量，sd表示下降子序列的数量
{
    if(su+sd>=ans) return;//加入当前的次数比最小值还大，则return
    if(u==n)//否则到了末尾，更新最小值
    {
        ans=su+sd;
        return;
    }
    //假如加到上升子序列中
    int k=0;
    while(k<su&&up[k]>=a[u]) k++;
    int t=up[k];//把当前数存下来，用来回溯
    up[k]=a[u];//更新当前的末尾
    if(k<su) dfs(u+1,su,sd);//假如不需要开辟新子序列
    else dfs(u+1,su+1,sd);//假如开辟新子序列
    up[k]=t;//回溯
    //假如加到下降子序列中，做法与上升相同，只不过把大于等于改小于等于
    k=0;
    while(k<sd&&down[k]<=a[u]) k++;
    t=down[k];
    down[k]=a[u];
    if(k<sd) dfs(u+1,su,sd);
    else dfs(u+1,su,sd+1);
    down[k]=t;
}
int main()
{
  while(cin>>n,n)
  {
    for(int i=0;i<n;i++) cin>>a[i];
    ans=n;
    dfs(0,0,0);
    cout<<ans<<endl;
  }
    return 0;
}

 

8  最长公共上升子序列 （最长公共子序列+最长上升子序列）

272. 最长公共上升子序列 - AcWing题库

 

1）朴素版（容易TLE）

 

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N],f[N][N];
int main()
{
  int n,ans=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
  {
      f[i][j]=f[i-1][j];//所有不包含a[i]的最长公共上升子序列
      if(a[i]==b[j])//所有包含a[i]的最长公共上升子序列
      {
          f[i][j]=max(f[i][j],1);//当空的时候是自己，也就是1
          for(int k=1;k<j;k++)//求最长公共上升子序列
            if(b[k]<b[j])
                f[i][j]=max(f[i][j],f[i][k]+1);
      }
  }
  //求最大值,第一个序列的前n个字母，与b的匹配最大
  for(int i=1;i<=n;i++) ans=max(ans,f[n][i]);
 printf("%d\n",ans);
    return 0;
}

 

2) 分析优化一维

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N],f[N][N];
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  for(int i=1;i<=n;i++)
  {
      int maxf=1;//由于在k中重复求前j个最大值,所有用一个maxf记录前j个的最长上升子序列的最大值
      for(int j=1;j<=n;j++)
    {
         f[i][j]=f[i-1][j];//所有不包含a[i]的最长公共上升子序列
      if(a[i]==b[j]) f[i][j]=max(f[i][j],maxf);//所有包含a[i]的最长公共上升子序列,更新最大值
      if(b[j]<a[i])  maxf=max(maxf,f[i][j]+1);//因为a[i]==b[j]的时候更新最大值，所以可以把b[j]换成a[i],用来与新的b[j]比较
    }
  }
  //最后更新一遍最大值
  int ans=0;
  for(int i=1;i<=n;i++) ans=max(ans,f[n][i]);
 printf("%d\n",ans);
    return 0;
}

 

3) 滚动数组优化二维数组变成一维

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N],f[N];
int main()
{
  int n,ans=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  for(int i=1;i<=n;i++)
     for(int j=1,maxf=1;j<=n;j++)
      {
          //因为更新f[i][j]的时候只用到了上一维f[i-1][j]的信息,故可以优化变成一维
        if(a[i]==b[j]) f[j]=max(f[j],maxf);
        if(b[j]<a[i])  maxf=max(maxf,f[j]+1);
      }
  //求一遍最大值
  for(int i=1;i<=n;i++) ans=max(ans,f[i]);
  printf("%d\n",ans);
    return 0;
}