Cod sursa(job #1728736)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 13 iulie 2016 16:24:17
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#define NR 10000
using namespace std;

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

int dp[NR][NR],a[NR],b[NR],vAux[NR],m,n,iv=0;

void scrieMatrice(int a[],int b[],int m,int n)
{
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            if(a[i]==b[j])
                dp[i][j]=1+dp[i-1][j-1];
            else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

void citire(int a[],int n)
{
    for(int i=1; i<=n; i++)
        f>>a[i];
}

void getSubsit()
{
    int i=m,j=n;
    while(dp[i][j]!=0)
    {
        if(a[i]==b[j])
        {
            vAux[++iv]=a[i];
            i--;
            j--;
        }
        else if(dp[i][j]==dp[i-1][j]) i--;
        else if(dp[i][j]==dp[i][j-1]) j--;
    }
}

void getSubsitRecursiv(int i,int j)
{
    if(dp[i][j]!=0){
        if(dp[i][j]!=dp[i-1][j-1])
        {
            getSubsitRecursiv(i-1,j-1);
            g<<a[i]<<" ";
        }
        else if(dp[i][j]==dp[i-1][j]) getSubsitRecursiv(i-1,j);
        else if(dp[i][j]==dp[i][j-1]) getSubsitRecursiv(i,j-1);
}
}

int main()
{
    f>>m>>n;
    citire(a,m);
    citire(b,n);
    scrieMatrice(a,b,m,n);
    g<<dp[m][n];
    g<<"\n";
    //getSubsit();
    //for(int i=iv; i>=1; i--)
        //g<<vAux[i]<<" ";
    getSubsitRecursiv(m,n);


    return 0;
}