Cod sursa(job #2131991)

Utilizator mihaicivMihai Vlad mihaiciv Data 15 februarie 2018 11:32:35
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int n,m,D[1300][1300],v1[1300],v2[1300],d[1301];
void citire() {
    f>>n>>m;
    for (int i=1;i<=n;i++) {
        f>>v1[i];
    }
    for (int i=1;i<=m;i++) {
        f>>v2[i];
    }
}
void rez() {
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (v1[i]==v2[j]) {
                D[i][j]=D[i-1][j-1]+1;
            }
            else {
                D[i][j]=max(D[i-1][j],D[i][j-1]);
            }
        }
    }
    /*
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cout<<D[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    int Answ=D[n][m];
    int posi=n;
    int posj=m;
    int Nr=0;
    while (posi>=1 && posj>=1) {
        if (D[posi-1][posj-1]+1==D[posi][posj] && posi>1 && posj>1) {
            posi--;
            posj--;
            d[++Nr]=v1[posi+1];
        }
        else {
            if (D[posi][posj]==D[posi-1][posj]+1 && posi>1) {
                posi--;
                d[++Nr]=v1[posi+1];

            }
            else if (D[posi][posj]==D[posi][posj-1]+1 && posj>1){
                posj--;
                d[++Nr]=v2[posj+1];
            }
            else if ( (D[posi-1][posj]>D[posi][posj-1] && posi>1) || posj==1 ) {
                posi--;
            }
            else {
                posj--;
            }
        }
    }
    g<<Answ<<"\n";
    for (int i=Answ;i>=1;i--) {
        g<<d[i]<<" ";
    }
}
int main() {
    citire();
    rez();
    return 0;
}