Cod sursa(job #2211097)

Utilizator DanSDan Teodor Savastre DanS Data 9 iunie 2018 13:24:37
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int MAX = 1025;
int a[MAX], na, b[MAX], nb, dp[MAX][MAX];

int main()
{
    in>>na>>nb;
    for(int i=na; i>=1; i--)
        in>>a[i];
    for(int j=nb; j>=1; j--)
        in>>b[j];
    for(int i=1; i<=na; i++)
        for(int j=1; j<=nb; j++)
        {
            if(a[i] == b[j])
                dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    out<<dp[na][nb]<<'\n';
    while(dp[na][nb]>0)
    {
        if(a[na]==b[nb])
        {
            out<<a[na]<<' ';
            --na; --nb;
        }
        else if(dp[na][nb] == dp[na-1][nb])
            --na;
        else --nb;
    }
    return 0;
}