Cod sursa(job #2151592)

Utilizator SahMatCodrea Andrei SahMat Data 4 martie 2018 17:37:54
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;
ifstream fi("cmlsc.in");
ofstream fo("cmlsc.out");
int n,m;
int a[1030];
int b[1030];
int c[1030];
int dp[1030][1030];
int k;

bool verif(int i)
{
    for(int t=1;t<=k;t++)
        if(a[i]==c[t])
        return false;
    return true;
}

int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
    fi>>a[i];
    for(int i=1;i<=m;i++)
    fi>>b[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;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]);
    }


//
//    for(int i=1;i<=n;i++)
//        {for(int j=1;j<=m;j++)
//        fo<<dp[i][j]<<" ";
//        fo<<endl;
//        }
    k=1;
    for(int i=1;i<=n;i++)
        {
        for(int j=1;j<=m;j++)
    {
        if(dp[i][j]==k and a[i]==b[j] and k<=dp[n][m])
        {
                if(verif(i))
            c[k++]=a[i];

        }

    }
        }
        fo<<dp[n][m]<<'\n';
        for(int i=1;i<=k-1;i++)
            fo<<c[i]<<" ";

    return 0;
}