Cod sursa(job #2013065)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 august 2017 13:50:57
Problema Cel mai lung subsir comun Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> A, B, res;
int DP[1050][1050], N, M;

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

    scanf("%d%d", &N, &M);
    A.resize(N + 1);
    B.resize(N + 1);

    for (int i = 1; i <= N; ++i) {
        scanf("%d", &A[i]);
    }
    for (int i = 1; i <= M; ++i) {
        scanf("%d", &B[i]);
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (A[i] == B[j]) {
                DP[i][j] = max(DP[i][j], DP[i-1][j-1] + 1);
            }
            else {
                DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
            }
        }
    }

    printf("%d\n", DP[N][M]);
    int i = N, j = M;
    while (i && j) {
        if (A[i] == B[j]) {
            res.push_back(A[i]);
            --i;
            --j;
        }
        else {
            if( DP[i][j-1] >= DP[i-1][j] ) {
                --j;
            }
            else {
                --i;
            }
        }
    }
    reverse(res.begin(), res.end());
    for (auto it : res)
        printf("%d ", it);
    printf("\n");

    return 0;
}