首页 > 代码库 > 10D-最长上升公共子序列

10D-最长上升公共子序列

#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int a[505], b[505];int dp[505], path[505];int Susake_lcs[505][505], Susake_lcis[505][505];void Susake_LCS(int *s1, int *s2, int m, int n){    memset(Susake_lcs, 0, sizeof(Susake_lcs));    memset(path, 0, sizeof(path));    int k = 0;    for(int i = 2; i <= m + 1; i++)        for(int j = 2; j <= n + 1; j++)        {            if(s1[i - 1] == s2[j - 1])            {                Susake_lcs[i][j] = Susake_lcs[i - 1][j - 1] + 1;                k++;                path[k] = s1[i - 1];            }            else if(Susake_lcs[i - 1][j] > Susake_lcs[i][j - 1])                Susake_lcs[i][j]= Susake_lcs[i - 1][j];            else                Susake_lcs[i][j] = Susake_lcs[i][j - 1];        }    if(k == 1)        printf("%d\n", path[1]);    else    {        for(int i = k; i >= 2; i--)            printf("%d ", path[i]);        printf("%d\n", path[1]);    }}void Susake_LCIS(int a[], int la, int b[], int lb){    memset(path, 0, sizeof(path));    memset(Susake_lcis, 0, sizeof(Susake_lcis));    memset(dp, 0, sizeof(dp));    int i, j, k, Max;    for(i = 1; i <= la; i++) {        memcpy(Susake_lcis[i], Susake_lcis[i-1], sizeof(Susake_lcis[0]));        for(k = 0, j = 1; j <= lb; j++)        {            if(b[j - 1] < a[i - 1] && dp[j] > dp[k]) k = j;            if(b[j - 1] == a[i - 1] && dp[k] + 1 > dp[j])            {                dp[j] = dp[k] + 1,                Susake_lcis[i][j] = i * (lb + 1) + k;            }        }    }    for(Max = 0, i = 1; i <= lb; i++)        if(dp[i] > dp[Max])            Max = i;    for(i = la * lb + la + Max, j = dp[Max]; j; i = Susake_lcis[i / (lb + 1)][i % (lb + 1)], j--)        path[j] = b[i % (lb + 1) - 1];    printf("%d\n", dp[Max]);    if(Max)    {        if(dp[Max] == 1)            printf("%d\n", path[1]);        else        {            for(int i = 1; i <= dp[Max] - 1; i++)                printf("%d ", path[i]);            printf("%d\n", path[dp[Max]]);        }    }}int main(int argc, char *argv[]){    int n, m;    while(scanf("%d", &n) != EOF)    {        memset(a, 0, sizeof(a));        memset(b, 0, sizeof(b));        for(int i = 0; i < n; i++) scanf("%d", &a[i]);        scanf("%d", &m);        for(int i = 0; i < m; i++) scanf("%d", &b[i]);        Susake_LCIS(a, n, b, m);    }    return 0;}

 

10D-最长上升公共子序列