Cod sursa(job #2222557)

Utilizator david.sachelarieDavid Sachelarie david.sachelarie Data 17 iulie 2018 12:09:23
Problema Cel mai lung subsir comun Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>

int v1[1024],v2[1024],mat[1024][1024],sir[1024];

int main()
{
    FILE *fin,*fout;
    fin = fopen("cmlsc.in" ,"r");
    fout = fopen("cmlsc.out" ,"w");

    int n,m,i;
    fscanf(fin, "%d%d" ,&n,&m);
    for(i=0;i<n;i++)
        fscanf(fin, "%d" ,&v1[i]);
    for(i=0;i<m;i++)
        fscanf(fin, "%d" ,&v2[i]);

    int j;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(v1[i]==v2[j]){
                if(i==0 || j==0)
                    mat[i][j]=1;
                else
                    mat[i][j]=mat[i-1][j-1]+1;
            }
            else{
                if(i==0 && j!=0)
                    mat[i][j]=mat[i][j-1];
                else if(i!=0 && j==0)
                    mat[i][j]=mat[i-1][j];
                else if(i!=0 && j!=0){
                    if(mat[i-1][j]>mat[i][j-1]) mat[i][j]=mat[i-1][j];
                    else mat[i][j]=mat[i][j-1];
                }
            }
        }
    }
    /*for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            fprintf(fout, "%d" ,mat[i][j]);
        }
        fprintf(fout, "\n");
    }*/

    i=n-1;
    j=m-1;
    int k=0,flag=0;
    while(flag==0){
        if(v1[i]==v2[j]){
            sir[k]=v1[i];
            i--; j--; k++;
        }
        else if(i<=0 && j<=0) flag=1;
        else if(i==0) j--;
        else if(j==0) i--;
        else if(mat[i-1][j]>mat[i][j-1]) i--;
        else j--;
    }

    fprintf(fout, "%d\n" ,k);
    k--;
    while(k>=0){
        fprintf(fout, "%d " ,sir[k]);
        k--;
    }
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}