Nu aveti permisiuni pentru a descarca fisierul grader_test2.in

Cod sursa(job #1003940)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 1 octombrie 2013 19:53:49
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *in,*out;
int n,m,i,j,raspuns[1025];
int sir1[1025], sir2[1025],mat[1025][1025],u=-1;
int main()
{
    in=fopen("cmlsc.in","rt");
    out=fopen("cmlsc.out","wt");
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=n;i++)
        fscanf(in,"%d",&sir1[i]);
    for(i=1;i<=m;i++)
        fscanf(in,"%d",&sir2[i]);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(sir1[i]==sir2[j])
            {
                mat[i][j]=mat[i-1][j-1]+1;

            }
            else
                mat[i][j]=max(mat[i-1][j], mat[i][j-1]);
        }

    fprintf(out,"%d",mat[n][m]);
    fprintf(out,"\n");
    i=n;
    j=m;
    while(i && j)
    {
        if(sir1[i]==sir2[j])
        {
            raspuns[++u]=sir1[i];
            i--;
            j--;
        }
        else if(mat[i][j-1]>mat[i-1][j])
            j--;
        else
            i--;

    }
    for(i=u;i>=0;i--)
        fprintf(out,"%d ",raspuns[i]);


    fclose(in);
    fclose(out);
    return 0;
}