Blog of CodeJELLOW’S ENGINEERING NOTES
← 返回文章

最长公共单调上升子序列

既然有了最长上升子序列,就补充一个最长公共上升子序列

本文目录 ⌄

    既然有了最长上升子序列,就补充一个最长公共上升子序列

    题面:给两个序列a,b长度分别为n,m求他们的最长公共单调上升子序列的长度。

    对于上升子序列不了解的可以去看之前CZT的文章。公共的意思是这个序列在A,B中均有出现,例如有A序列为4 3 2 1 7 8 9,B序列为7 8 9 4 3 2 1,其最长公共子序列是4 3 2 1,而最长最长公共单调上升子序列应该是 7 8 9。当然这题在两个数相等时也可以判断为单调上升的。


    先来说说最长公共子序列,这是一道比较经典的dp题,我们可以很容易写出

    1.状态F[i][j]表示a序列匹配到第i个b序列匹配到第j个的最长长度

    2.状态转移方程

    F[i][j] = max(F[i-1][j] , F[i][j-1]) (a[i] != b[j])

    F[i][j] = F[i-1][j-1]+1(a[i] = b[j])

    答案就在F[n][m]中

    代码
    TEXT
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,f[5010][5010];
    char a[5010],b[5010];
    int main(){
        scanf("%s",a+1);
        scanf("%s",b+1);
        n=strlen(a+1);
        m=strlen(b+1);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
            }
        }
        printf("%d",f[n][m]);
        return 0;
    }

    然后我们再来考虑最长公共上升子序列

    1.定义状态:F[x][y]表示a串匹配长度x,b串匹配长度y,且以b[j]结尾的序列长度。

    2.状态转移方程:

    F[i][j]=F[i][j] = F[i-1][j] (a[i] != b[j])

    F[i][j] = max(F[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])

    对于第一个方程我们可以理解为当a[i]!=a[j]时我们用b序列去匹配a序列匹配失败了则a[i]这个数是对这个序列没有贡献的,即考虑不考虑都无所谓

    对于第二个方程我们可以理解为当b序列中第j个数匹配了,我们可以选择前面所有的状态进行转移,但是保证 b[j] > b[k]

    代码
    TEXT
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,ans,a[3010],b[3010],f[3010][3010];
    int main(){
    	scanf("%d %d",&n,&m);
    	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
    	for(int i=1;i<=n;++i){
    		for(int j=1;j<=m;++j){
    			f[i][j]=f[i-1][j];
    			if(a[i]==b[j]){
    				int maxn=0;
    				for(int k=1;k<=j-1;++k){
    					if(b[j]>b[k]) maxn=max(maxn,f[i-1][k]);
    				}
    				f[i][j]=maxn+1;
    			} 
    		}
    	}
    	for(int i=1;i<=m;++i) ans=max(ans,f[n][i]);
    	printf("%d",ans);
    	return 0;
    }

    但是这样的做法在最坏情况下可能到达O(n^3),我们可以考虑优化,我们可以发现在第三重循环找最大值时是否可以进行一定优化?

    我们可以发现当有一个序列a[i]=b[j]时看第二个转移方程b[j] > b[k]也就是说a[i]>b[k],我们可以利用一个最大值maxn来存下每次的最大值,即当a[i]>b[j]时更新它,当a[i]=b[j]时f[i][j]=maxn+1;

    代码
    TEXT
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,ans,a[3010],b[3010],f[3010][3010];
    int main(){
    	scanf("%d %d",&n,&m);
    	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
    	for(int i=1;i<=n;++i){
    		int maxn=0;
    		for(int j=1;j<=m;++j){
    			f[i][j]=f[i-1][j];
    			if(a[i]>b[j]) maxn=max(maxn,f[i-1][j]);
    			if(a[i]==b[j]) f[i][j]=maxn+1;
    		}
    	}
    	for(int i=1;i<=m;++i) ans=max(ans,f[n][i]);
    	printf("%d",ans);
    	return 0;
    }

    我们依然可以发现f[i][j]转移只用到了f[i][j-1]的数,我们可以再进行优化!利用滚动数组优化我们的空间。

    代码
    TEXT
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,ans,a[3010],b[3010],f[3010];
    int main(){
    	scanf("%d %d",&n,&m);
    	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
    	for(int i=1;i<=n;++i){
    		int maxn=0;
    		for(int j=1;j<=m;++j){
    			if(a[i]>b[j]) maxn=max(maxn,f[j]);
    			if(a[i]==b[j]) f[j]=maxn+1;
    		}
    	}
    	for(int i=1;i<=m;++i) ans=max(ans,f[i]);
    	printf("%d",ans);
    	return 0;
    }

    这个就是最终的代码了,如果是只能递增不能相等的话,只需要在此基础上修改即可,这里就不放代码了。

    通过 RSS 订阅更新 →