LIS LCS（动态规划)

Zandra ·

更新时间:2024-11-13

· 673 次阅读

问题描述

东东有两个序列A和B。

他想要知道序列A的LIS和序列AB的LCS的长度。

注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。

Input

第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）
第二行n个数，表示序列A
第三行m个数，表示序列B

Output

输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度

解题思路

这个题是基本的动态规划问题，LIS是最长上升子序列，LCS是最长公共子序列。

求解LIS就是设dp[i]为以当前元素结尾的最长上升序列，那么dp[i]=max(dp[j]∣j<i&&a[j]<a[i])+1dp[i]=max(dp[j] | j<i \&\& a[j]<a[i])+1dp[i]=max(dp[j]∣j<i&&a[j]<a[i])+1，最终答案就是max(dp[i],i=1...n)max(dp[i],i=1...n)max(dp[i],i=1...n)。

而求解LCS则是遍历两个序列，设dp[i][j]dp[i][j]dp[i][j]是到第一个序列的第iii个元素，第二个序列的第jjj个元素为止，最长的公共子序列。如果a[i]==a[j]a[i]==a[j]a[i]==a[j]，那么我们就有dp[i][j]=dp[i−1][j−1]dp[i][j]=dp[i-1][j-1]dp[i][j]=dp[i−1][j−1]，否则有dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j]=max(dp[i-1][j],dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])。因此最终结果是dp[n][m]dp[n][m]dp[n][m]。

完整代码

//#pragma GCC optimize(2)
//#pragma G++ optimize(2)
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=5000+10;
int n,m,a[maxn],b[maxn],dp1[maxn],dp2[maxn][maxn],ans;
int getint(){
    int x=0,s=1; char ch=' ';
    while(ch'9'){ ch=getchar(); if(ch=='-') s=-1;}
    while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar();}
    return x*s;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    n=getint(); m=getint();
    for (int i=1; i<=n; i++) a[i]=getint(),dp1[i]=1;
    for (int i=1; i<=m; i++) b[i]=getint();
    for (int i=1; i<=n; i++){
        for (int j=1; j<i; j++)
            if(a[j]<a[i]) dp1[i]=max(dp1[i],dp1[j]+1);
        ans=max(ans,dp1[i]);
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if(a[i]==b[j]) dp2[i][j]=dp2[i-1][j-1]+1;
            else dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1]);
        }
    }
    printf("%d %d\n",ans,dp2[n][m]);
    return 0;
}

作者：龙征天

动态规划动态

1024 个赞