Cod sursa(job #1642785)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 9 martie 2016 16:10:49
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define NMax 1025

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

int n, m;
vector<short> A;
vector<short> B;
short C[NMax][NMax];
vector<short> sol;

void dodp() {
    for (int i=0;i<=n;i++)
        C[0][i] = 0;
    for (int i=0;i<=m;i++)
        C[i][0] = 0;

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (A[i] == B[j]) {
                C[i][j] = 1+C[i-1][j-1];
            } else {
                C[i][j] = max(C[i][j-1], C[i-1][j]);
            }
        }
    }

    g<<C[n][m]<<'\n';

    int i=n;
    int j=m;
    while (i > 1 || j > 1) {
        if (C[i][j] == 1+C[i-1][j-1]) {
            sol.pb(A[i]);
            i--; j--;
        } else {
            if (C[i][j] == C[i-1][j])
                i--;
            else
                j--;
        }
    }

    for (int p=sol.size()-1;p>=0;p--) {
        g<<sol[p]<<' ';
    }
    g<<endl;
}

void read() {
    f>>n>>m;
    A.pb(0); B.pb(0);
    for (int i=1;i<=n;i++) {
        int x; f>>x;
        A.pb(x);
    }

    for (int i=1;i<=m;i++) {
        int x; f>>x;
        B.pb(x);
    }
}

int main() {

    read();
    dodp();

    f.close(); g.close();
    return 0;
}