Cod sursa(job #525849)

Utilizator cristian9Cristian Zloteanu cristian9 Data 26 ianuarie 2011 16:05:07
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
int v[1025],u[1025],n,m, sol[1025], z=1;
int mat[1025][1025],mav;

void afiseaza(int i,int j){
    if(mat[i][j])
        if(v[i]==u[j]){
            afiseaza(i-1,j-1);
            //printf("%d ", v[i]);
            sol[z++]=v[i];
        }
    else{
        if(mat[i][j]==mat[i-1][j])
            afiseaza(i-1,j);
        else
            if(mat[i][j]==mat[i][j-1])
                afiseaza(i,j-1);
    }
}


int main(){
    freopen ("cmlsc.in", "r", stdin);
    freopen ("cmlsc.out", "w", stdout);

    int i, j, l;
    scanf("%d %d ", &n, &m);

	for(i=1; i<=n+m; i++){
		if(i<=n)
			scanf("%d ", &v[i]);
		else
			scanf("%d ", &u[i-n]);
	}

	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(v[i]==u[j])
				mat[i][j]=mat[i-1][j-1]+1;
			else
				if(mat[i-1][j]>mat[i][j-1])
					mat[i][j]=mat[i-1][j];
				else
					mat[i][j]=mat[i][j-1];

    afiseaza(n,m);
    printf("%d\n", z-1);
    for(i=1; i<z; i++)
        printf("%d ", sol[i]);
    return 0;
}