Cod sursa(job #2429947)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 11 iunie 2019 22:19:58
Problema Cel mai lung subsir comun Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <iostream>
#define MAX 1026

using namespace std;

int a[MAX], b[MAX], dp[MAX][MAX], sol[MAX];

int main()
{
    int n, m, i, j, contor = 0;

    ifstream fin("cmlsc.in");
    ofstream fout("cmlsc.out");

    fin >> n >> m;

    for(i = 1; i <= n; i++)fin >> a[i];

    for(i = 1; i <= m; i++)fin >> b[i];

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            cout << dp[i][j] << " ";

        cout << '\n';
    }

    fout << dp[n][m] << '\n';

    i = n;
    j = m;
    while(i > 0 && j > 0)
    {
        if(a[i] == b[j])
        {
            sol[contor] = a[i];
            i--;
            j--;
            contor++;
        }
        else if(dp[i - 1][j] == dp[i][j])i--;
        else if(dp[i][j - 1] == dp[i][j])j--;
    }

    for(i = contor - 1; i >= 0; i--)fout << sol[i] << " ";

    fin.close();
    fout.close();

    return 0;
}