最长上升子序列基础模型

一.最长上升子序列问题定义

如字面含义,对于a1,a2,a3,a4…,求出最长的递增的序列,递减的序列反向就相当于递增

---

二.最长上升子序列代码模板

注：下面的代码是默认两个相同高度的平台之间不能跳跃,具体看if判断里面是否有等于号,如果是求最长下降子序列,那就把大于号换成小于号

1.朴素版O(n^2)

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int dp[N],a[N];
    int main(){
        int n;
        cin>>n;
        for(int i=1;i<n;i++)
            cin>>a[i]; 
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(a[i]>a[j]){
                    dp[i]=max(dp[i],dp[j]+1); 
                }
            }
            ans=max(dp[i],ans);
        }
        cout<< ans+1;//起始点要算进去所以要+1
    }

2.进阶版(nlogn)(默认数据非负数)

#include<bits/stdc++.h>
using namespace std;
const int N=101000;
int dp[N],a[N],g[N],q[N];
int main(){
    int n=0,ans=0;
    while(cin>>a[n])n++;
    //此处输入的都是非负数
    q[0]=-2e9;
    for(int i=0;i<n;i++){
        int l=0,r=ans;
        while(l<r){
            int mid=(l+r+1)>>1;//下面是l=mid,所以这里要+1
            if(a[i]>q[mid])l=mid;
            else r=mid-1;
        }
    //根据两段性：q[r]是<a[i]的最大的数,所以q[r+1]>=a[i],用a[i]代替原来的值更好(或者是重新创建一个新的子序列)
        q[r+1]=a[i];
        ans=max(ans,r+1);
    }
     cout<<ans<<'\n';
}

---

三.由最长上升子序列延伸出来的问题+案例

1.求先递增再递减的最长序列

登山：https://www.acwing.com/problem/content/1016/

1.1题意分析：

由于要求的是严格先递增再递减的序列的最大长度,所以我们一定要找到那个极值点,找到极值点后唯一答案便确定了。所以,用若up[i]表示到i点的最长上升子序列,down[i]表示从i到n的最长下降子序列,只要循环求出最大的up[i]+down[i]即可

注意 :求down[i]的时候循环一定要逆向不能正向,因为下标大的down[i]是后更新的

1.2 AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int up[N],down[N],h[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
           if(h[i]>h[j])
                up[i]=max(up[i],up[j]+1);
     for(int i=n;i>=1;i--)//这里一定要倒着求注意dp值的更新必须用到已更新的dp值    
        for(int j=i+1;j<=n;j++)
           if(h[i]>h[j])
                down[i]=max(down[i],down[j]+1);   
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,up[i]+down[i]+1);
    cout<<ans;

}

2.最大上升子序列和

2.1 定义 :求所有上升子序列中和最大的子序列和

最大上升子序列和:https://www.acwing.com/problem/content/1018/

2.2 题意分析 :

用dp[i]表示到点时的最大子序列和,但是由于可能出现负数,所以当满足递增子序列的情况下,有转移和转移两种选择,故状态转移方程为 ：dp[i]=max(dp[i],dp[j]+a[i])

2.3 AC代码 :

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N],a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=0;
    for(int i=0;i<n;i++){
        dp[i]=a[i];
       for(int j=0;j<i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+a[i]);
            }
        }
        ans=max(dp[i],ans);
    }
     cout<<ans;
} 

3.最小下降自序列(可相等)个数覆盖整个序列

3.1. 定义 :

用最少个数的不上升子序列的个数覆盖整个序列

3.2 拦截导弹https://www.acwing.com/problem/content/1012/

3.3 解法分析

1.用g数组来维护每个子序列的末尾值(即最小值)且严格满足单调递增(稍微模拟理解一下就知道了)
2.然后对于每个a[i],从到到尾扫描g数组，看看当前创建的子序列的末尾值是否大于a[i] (我们的目的是通过贪心,让a[i]插到末尾值最小的序列当中去)
3.
如果大于就肯定是最小的大于a[i],直接退出循环,否则就一个搜索到尽头,这个时候如果k>=cnt(严格来说就是等于),那么就重新开一个子序列,否则的用更小的数代替当前子序列的末尾数g[i]

3.4 AC代码(数据都是非负数)

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N],a[N],g[N];
int main(){
    int n=0,ans=0;
    while(cin>>a[n])n++;
    //此处输入的都是非负数 
    for(int i=0;i<n;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]<=a[j])
                dp[i]=max(dp[i],dp[j]+1); 
            }

        ans=max(dp[i],ans);
        }
     cout<<ans<<'\n';

     //g数组表示的是每个子序列的末尾的那个数(最小值),每次循环都要初始化k然后从头往后搜索g
     int cnt=0;
     for(int i=0;i<n;i++){
         int k=0;
         while(k < cnt&&g[k] < a[i]) //g数组满足严格单调递增
             k++;
        g[k]=a[i];
        if(k>=cnt)cnt++; 
     }
     cout<<cnt;
} 

注意：
1.这题的代码时可以用最长上升子序列模板的优化版的
2.如果题目不允许相等,那么while循环那里要加等于号

最小子序列个数问题的升级版：导弹防御系统https://www.acwing.com/problem/content/189/
我不多做解释，就是加了一个dfs,要注意还原现场就好

4.最长上升公共子序列

模板题 ：https://www.acwing.com/problem/content/274/
4.1 代码分析
1.dp[i][j]的含义 :第一个序列的前i项,第二个序列的前 j项,当b[j]必定被选取的时候的最长公共子序列
2.所以对于dp[i][j]的状态转移方程,只可能从a[i]==b[j]和a[i]!=b[j]中选
3.朴素版的代码就是最长公共子序列和最长上升子序列问题的直接结合
4.优化版中对i相同时,前j个

4.2 AC代码
朴素版(最坏O^3)

#include<algorithm>
#include<iostream>
using namespace std;
const int N=3010;
int dp[N][N],a[N],b[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++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            if(a[i]==b[j]){
                dp[i][j]=max(dp[i][j],1);//b[i]不继承,只有他一个的时候是dp值为1
                for(int k=1;k<j;k++){
                    if(b[j]>b[k])
                        dp[i][j]=max(dp[i][j],dp[i][k]+1);
    //准确的说应该是dp[i][k]其中a[i]和b[k]不相等的情况转移过来,但是因为a[i]==b[j]>b[k],所以满足条件 
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
    printf("%d",ans);
}

优化版O(n^2)

#include<algorithm>
#include<iostream>
using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];//f[i][j]表示a序列长度为i且公共子序列的最后一个数字时b[j]的时候最长公共上升序列长度 
int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    for (int i = 1; i <= n; i ++ )//先定下a序列长度 
    {
        int maxv = 1;//maxv表示的是dp[i][1到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], maxv);
    //上面maxv的含义是a[i]>b[j-1]的所有f[i][j-1]+1的最大值
            if (b[j] < a[i])//为下一个b[j]>a[i]作准备
                maxv = max(maxv,f[i][j]+1);
    //maxv之前已经遍历了1到j-1,a[i]与当前b[j]不匹配,所以当遇到下一个a[i]==b[j]的时候再使用maxv,而maxv在这里已经更新好了
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res << endl; 
    return 0;
}