Cod sursa(job #2272972)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 30 octombrie 2018 20:17:55
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda alexei1 Marime 0.78 kb
#include <fstream>

using namespace std;

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

const int DM =  1025;

int X[DM],Y[DM];
int dp[DM][DM];
int nra;
int afis[DM];

int main()
{
    int nrelx,nrely;
    fin >> nrelx >> nrely;
    for(int i = 1; i <= nrelx; i++) fin >> X[i];
    for(int i = 1; i <= nrely; i++) fin >> Y[i];
    
    for(int i = 1; i <= nrelx; i++)
        for(int j = 1; j <= nrely; j++)
            if(X[i] == Y[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
    
    for(int i = nrelx, j = nrely; i && j; )
        if(X[i] == Y[j]) afis[++nra] = X[i], i--, j--;
        else if(dp[i][j - 1] > dp[i - 1][j]) j--;
        else i--;
    
    for(int i = nra; i >= 1; i--) fout << afis[i] << " ";
    
    return 0;
}