Cod sursa(job #1370429)

Utilizator gapdanPopescu George gapdan Data 3 martie 2015 14:33:35
Problema Cel mai lung subsir comun Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <vector>
#define NMAX  1005

using namespace std;

int n,m;
int a[NMAX],b[NMAX];
int s[NMAX][NMAX],drum[NMAX][NMAX];
vector<int>sol;

int main()
{
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
    for(int i = 1; i <= m; ++i) scanf("%d",&b[i]);

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if (a[i] == b[j])
            {
                s[i][j] = s[i-1][j-1] + 1;
                drum [i][j] = 1;
            }
            else if (s[i-1][j] > s[i][j-1])
                {
                    s[i][j] = s[i-1][j];
                    drum[i][j] = 2;
                }
                else
                {
                    s[i][j] = s[i][j-1];
                    drum[i][j] = 3;
                }
        }
    printf("%d\n", s[n][m]);
    int i=n,j=m;
    while( i > 0 && j > 0)
    {
        if (drum[i][j] == 1) {sol.push_back(a[i]);--i;--j;}
            else
            {
                if (drum[i][j] == 2) --i;
                    else --j;
            }
    }

    for(int i = sol.size() - 1; i >= 0 ; --i) printf("%d ",sol[i]);
    return 0;
}