Cod sursa(job #1522940)

Utilizator fluture.Gafton Mihnea Alexandru fluture. Data 12 noiembrie 2015 10:31:55
Problema Cel mai lung subsir comun Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
///Optimizare short int si char

#include <cstdio>
#include <algorithm>

#define NMAX 1027
#define in "cmlsc.in"
#define out "cmlsc.out"
#define shd short int

using namespace std;
int n1, n2;
shd v1[NMAX], v2[NMAX], dp[NMAX][NMAX];

inline void dinamica()
{
    for(int i = 1; i<= n1; ++i)
    {
        for(int j = 1; j<= n2; ++j)
        {
            if(v1[i] == v2[j]) {dp[i][j] = dp[i-1][j-1]+1; continue;}
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}
void reconstituire(const int &x, const int &y)
{
    if(dp[x][y] == 0) return ;
    if(dp[x-1][y-1]  == dp[x][y])
    {
        reconstituire(x-1, y-1);
        return ;
    }
    if(dp[x-1][y] > dp[x][y-1])
    {
        reconstituire(x-1, y);
        return ;
    }
    if(dp[x][y-1] > dp[x-1][y])
    {
        reconstituire(x, y-1);
        return ;
    }
    if(dp[x-1][y-1] == dp[x][y] - 1)
    {
        reconstituire(x-1, y-1);
        printf("%d ", v1[x]);
        return ;
    }
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &n1, &n2);
    for(int i = 1; i<= n1; ++i) scanf("%hd", &v1[i]);
    for(int i = 1; i<= n2; ++i) scanf("%hd", &v2[i]);
    dinamica();
    printf("%hd\n", dp[n1][n2]);
    reconstituire(n1, n2);
    printf("\n");
    return 0;
}