Cod sursa(job #1511995)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 27 octombrie 2015 16:19:36
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define Nmax 1027

using namespace std;

int a[Nmax],b[Nmax],dp[Nmax][Nmax],sir[Nmax];

inline void Read()
{
    int i;
    ifstream fin("cmlsc.in");
    fin>>a[0]>>b[0];
    for(i=1;i<=a[0];i++)
        fin>>a[i];
    for(i=1;i<=b[0];i++)
        fin>>b[i];
    fin.close();
}

inline void CMLSC()
{
    int i,j;
    for(i=1;i<=a[0];i++)
        for(j=1;j<=b[0];j++)
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

}

inline void Solve()
{
    int i,j,k;
    CMLSC();
    i=a[0];j=b[0];k=1;sir[0]=dp[a[0]][b[0]];
    for(i=a[0], j=b[0]; i;)
    {
        if(a[i]==b[j]) {sir[k++] = a[i]; i--;j--;}
        else if(dp[i-1][j]>dp[i][j-1]) i--;
        else j--;
    }
}

inline void Write()
{
    int i;
    ofstream fout("cmlsc.out");
    fout<<sir[0]<<"\n";
    for(i=sir[0];i>0;i--)
        fout<<sir[i]<<" ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}