首页 > 代码库 > 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-最长上升公共子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。