Cod sursa(job #2177369)

Utilizator Narvik13Razvan Roatis Narvik13 Data 18 martie 2018 14:43:58
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#define nmax 1026

using namespace std;

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

int n1, n2, dp[nmax][nmax], v1[nmax], v2[nmax];
vector <int> res;

void input()
{
    f >> n1 >> n2;
    for(int i = 1; i <= n1; ++i)
        f >> v1[i];
    for(int j = 1; j <= n2; ++j)
        f >> v2[j];
}

void din()
{
    for(int i = 1; i <= n1; ++i)
        for(int j = 1; j <= n2; ++j)
            if(v1[i] == v2[j])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

void back_din()
{
     int i = n1, j = n2;

     while(i > 0 && j > 0)
     {
         if(v1[i] == v2[j])
         {
             res.push_back(v1[i]);
             -- i;
             -- j;
         }
         else if(dp[i-1][j] > dp[i][j-1])
         {
             --i;
         }
         else
            -- j;
     }
}

void output()
{
    o  << res.size() << '\n';

    for(vector<int>::reverse_iterator it = res.rbegin(); it != res.rend(); ++it)
        o << *it << ' ';
}

int main()
{
    input();
    din();
    back_din();
    output();
    return 0;
}