dp，路径保存，最大公共上升子序列——ZOJ

题目含义

找两个序列共有的，单调递增的，最大的子序列

题目分析

两个长序列的情况，可以由两个短的序列发展而来，也就是可以用动态分析

令dp[i][j]表示第一条序列到ai，第二条序列到bj，同时bj是公共子序列的最后一项时的公共子序列长度

如果a[i]!=b[j]，那么dp[i][j]=dp[i-1][j]

如果a[i]==b[j],那么dp[i][j]=max(dp[i-1][k])+1,0<=k<j

而这个k在哪取呢，就是在上一次a[i]==b[j]时的j了

每次遇到a[i]==b[j]时，给它赋上前一个点的位置，这样就可以递归找到子序列了

题目代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=507;
LL a[maxn],b[maxn];
int t,n,m,dp[maxn][maxn];
struct node{
    int x,y;
}path[maxn][maxn];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%lld",&b[i]);
        for(int i=1;i<=n;i++){
            int mx=0,tx=0,ty=0;
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                path[i][j].x=i-1;
                path[i][j].y=j;
                if(a[i]==b[j]){
                    dp[i][j]=mx+1;
                    path[i][j].x=tx;
                    path[i][j].y=ty;
                }
                if(dp[i-1][j]>mx&&a[i]>b[j]){
                    mx=dp[i-1][j];
                    tx=i;
                    ty=j;
                }
            }
        }
        int mx=0,tx=n,ty;
        for(int i=1;i<=m;i++)
        if(dp[n][i]>mx){
            mx=dp[n][i];
            ty=i;
        }
        int save[maxn],cnt=0;
        while(dp[tx][ty]!=0){
            int tempx=path[tx][ty].x;
            int tempy=path[tx][ty].y;
            if(dp[tx][ty]!=dp[tempx][tempy])
                save[++cnt]=b[ty];
            tx=tempx;
            ty=tempy;
        }
        printf("%d
",mx);
        for(int i=cnt;i>0;i--)
            printf("%d ",save[i]);
        printf("
");
        if(t)printf("
");
    }
    return 0;
}