Cod sursa(job #2354130)

Utilizator mihai.alphamihai craciun mihai.alpha Data 24 februarie 2019 21:33:25
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

int m, n;
int d[1050][1050];
int a[1050], b[1050];
int prev1[1050];

int main()  {
    ifstream cin("cmlsc.in");
    ofstream cout("cmlsc.out");
    cin >> m >> n;
    for(int i = 1;i <= m;i++)
        cin >> a[i];
    for(int j = 1;j <= n;j++)
        cin >> b[j];
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= n;j++)  {
            d[i][j] = max(d[i - 1][j], d[i][j - 1]);
            if(a[i] == b[j])  {
                d[i][j] = max(d[i][j], d[i - 1][j - 1] + 1);
            }
        }
    int bst = 0;
    for (int i = m, j = n; i; )
        if (a[i] == b[j])
            prev1[++bst] = a[i], --i, --j;
        else if (d[i-1][j] < d[i][j-1])
            --j;
        else
            --i;
    cout << d[m][n] << "\n";
    for(int i = d[m][n];i >= 1;i--)
        cout << prev1[i] << " ";
    return 0;
}