Cod sursa(job #2364560)

Utilizator AplayLazar Laurentiu Aplay Data 4 martie 2019 09:41:34
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>

#define MAX_LENGTH 1025

int N, M, n[MAX_LENGTH], m[MAX_LENGTH], dp[MAX_LENGTH][MAX_LENGTH];

int maximum(int x, int y) {
    return x < y ? y : x;
}

void printLongestCommonSubsequence(int firstIndex, int secondIndex) {
    if (firstIndex < 1 || secondIndex < 1) return;
    if (n[firstIndex] == m[secondIndex]) {
        printLongestCommonSubsequence(firstIndex - 1, secondIndex - 1);
        printf("%d ", n[firstIndex]);
        return;
    }
    if (dp[firstIndex - 1][secondIndex] < dp[firstIndex][secondIndex - 1]) {
        printLongestCommonSubsequence(firstIndex, secondIndex - 1);
    } else {
        printLongestCommonSubsequence(firstIndex - 1, secondIndex);
    }
}

int main() {
    freopen("cmlsc.in", "r", stdin);
    freopen("cmlsc.out", "w", stdout);

    scanf("%d%d", &N, &M);
    for (int it = 1; it <= N; ++it) scanf("%d", &n[it]);
    for (int it = 1; it <= M; ++it) scanf("%d", &m[it]);

    for (int it = 1; it <= N; ++it) {
        for (int jt = 1; jt <= M; ++jt) {
            if (n[it] == m[jt]) dp[it][jt] = 1 + dp[it - 1][jt - 1];
            else dp[it][jt] = maximum(dp[it][jt - 1], dp[it -1][jt]);
        }
    }

    printf("%d\n", dp[N][M]);
    printLongestCommonSubsequence(N, M);

    return 0;
}