侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

最长公共上升子序列

Hope
2022-04-02 / 0 评论 / 0 点赞 / 323 阅读 / 1,547 字
温馨提示:
本文最后更新于 2022-04-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Acwing 272. 最长公共上升子序列

思路:

最长公共上升子序列.png

代码:

#include<iostream>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int j = 1; j <= n; j++) cin>>b[j];


    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            //不包含a[i]
            f[i][j] = f[i - 1][j];
            //包含a[i]
            int maxv = 1;
            if(a[i] == b[j]){
                //统计包含的情况下的最大值 最后与不包含的比较
                for(int k = 1; k < j; k++){
                    //maxv 统计1 ~ j - 1 中符合上升条件的 枚举 1 ~ j - 1中 只有前面的小于后面的才会去更新
                    if(b[k] < b[j]){
                        maxv = max(maxv,f[i - 1][k] + 1);
                    }
                }
                f[i][j] = max(f[i][j],maxv);
            }

        }
    }

    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res,f[n][i]);

    cout<<res<<endl;
    return 0;
}

上面的代码是三维的,我们在寻找1 ~ j - 1的过程中,对于每个j实际上都在重复的寻找,所以可以优化这一维。
下面这个条件进入的时候,是满足 a[i] == b[j]的所以,a[i] 可以换成b[j]

if(b[k] < b[j])

而k是从1递增到j的,遍历每个k的时候,只有满足 b[k] < b[j]才更新maxv,而b[j] == a[i],可以替换,所以是 b[k] < a[i],
image.png
但是这样的工作是重复的,所以可以进行下面的优化:

    for(int i = 1; i <= n; i++){
	//maxv 用来维护选择a[i]的情况
        int maxv = 1;
        for(int j = 1; j <= n; j++){
            //不包含a[i]
            f[i][j] = f[i - 1][j];
            //包含a[i] 以b[j]的上一个是什么来划分
            if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
	    //这里面的j实际上就是上面O(n^3)做法里面的k
            if(b[j] < a[i]) maxv = max(maxv,f[i - 1][j] + 1);
        }
    }

最终优化的代码如下:

#include<iostream>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int j = 1; j <= n; j++) cin>>b[j];


    for(int i = 1; i <= n; i++){
        int maxv = 1;
        for(int j = 1; j <= n; j++){
            //不包含a[i]
            f[i][j] = f[i - 1][j];
            //包含a[i] 以b[j]的上一个是什么来划分
            //if(b[j] < a[i]) maxv = max(maxv,f[i - 1][j] + 1);
            if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
            if(b[j] < a[i]) maxv = max(maxv,f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res,f[n][i]);

    cout<<res<<endl;
    return 0;
}

0

评论区