hdu1423LCIS zoj2432 必须掌握！

时间：2024-04-25 23:06:03

LCIS就是最长上升公共子序列，要结合LIS和LCS来求

LIS：f[j]=max(f[i])+1;

LCS:f[i,j]=max(f[i-1,j],f[i,j-1]或f[i-1,j-1]+1

那么对于LCIS，定义f[i][j]是以B[j]为结尾的最长公共上升子序列长度，

如果A[i]！=B[j]，那么f[i][j]=f[i-1][j]，

否则 f[i][j]=max(d[i-1][k])+1;1<=k<=j-1

最后扫描一次f[n][j],找到最大的

zoj2432需要用pre数组保存前驱pre[i][j]表示以b[j]结尾的上一个字符在b中的下标，即记录LCIS并输出





#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<string.h>

using namespace std;

const int maxn =  + ;

#define LL long long

int n, m;

LL a[maxn], b[maxn];

int f[maxn][maxn];

int pre[maxn][maxn];

int main()

{

    int T; cin >> T;

    while (T--) {

        scanf("%d", &n);

        for (int i = ; i <= n; ++i) scanf("%lld", a + i);

        scanf("%d", &m);

        for (int i = ; i <= m; ++i) scanf("%lld", b + i);

        memset(pre, -, sizeof(pre));

        memset(f, , sizeof(f));

        for (int i = ; i <= n; ++i) {

            int v = , k = ;

            for (int j = ; j <= m; ++j) {

        //        pre[i][j] = pre[i - 1][j];

                f[i][j] = f[i - ][j];

                if (a[i] > b[j] && v < f[i - ][j]) v = f[i - ][j], k = j;

                if (a[i] == b[j] && v + >f[i][j]) f[i][j] = v + , pre[i][j] = k;

            }

        }

        int k = ;

        for (int i = ; i <= m; ++i)

        if (f[n][i]>f[n][k]) k = i;

        printf("%d\n", f[n][k]);

        if (f[n][k] == ) continue;

        int i = n;

        vector<int> ans;

        for (int i = n; i >= ;--i)

        if (pre[i][k] != -) ans.push_back(a[i]), k = pre[i][k];

        printf("%d", ans.back());

        for (int i = ans.size() - ; i >= ; --i) printf(" %d", ans[i]);

        printf("\n");

    }

}






 


相关文章