Cod sursa(job #1318116)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 15 ianuarie 2015 17:11:26
Problema Cel mai lung subsir comun Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
using namespace std;

int N[1030],M[1030],n,m,sol[1030],d[1030][1030],lungime;


void citire(){

    int i;
    ifstream in("cmlsc.in");
    in>>n>>m;
    for(i=1;i<=n;i++)
        in>>N[i];
    for(i=1;i<=m;i++)
        in>>M[i];
    in.close();

}
void solve() {

    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(N[i]==M[j])
                d[i][j]=d[i-1][j-1]+1;
            else
                d[i][j]=max(d[i-1][j],d[i][j-1]);

    i=n;j=m;
    while(i) {
        if(N[i] == M[j]) {
            sol[++lungime]=N[i];
            i--;j--;
        }
        else {
            if(d[i-1][j]>d[i][j-1])
                i--;
            else
                j--;
        }

    }

}

void afisare() {

    ofstream out("cmlsc.out");
    int i;
    out<<lungime<<'\n';
    for(i=lungime;i>=1;i--)
        out<<sol[i]<<' ';
    out.close();

}


int main() {

    citire();
    solve();
    afisare();

}