Cod sursa(job #1598381)

Utilizator dodecagondode cagon dodecagon Data 12 februarie 2016 20:56:47
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

int dp[1030][1030],n,m,i,j,t[1030],s[1030],p[1030];

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

 scanf("%d %d",&n,&m);
 n++,m++;
 for (i=1;i<n;i++)
    scanf("%d",t+i);
 for (i=1;i<m;i++)
    scanf("%d",s+i);
 for (i=1;i<n;i++)
    for (j=1;j<m;j++)
      if (t[i]==s[j])
        dp[i][j]=dp[i-1][j-1]+1;else
         if (dp[i-1][j]>dp[i][j-1])
             dp[i][j]=dp[i-1][j];else
             dp[i][j]=dp[i][j-1];


    printf("%d\n",dp[n-1][m-1]);
    i=n-1;j=m-1;
    int k=dp[i][j];
    while (i)
    {
        if (t[i]==s[j])
            p[k--]=t[i],i--,j--; else
         if (dp[i-1][j]>dp[i][j-1])
            i--; else j--;
    }

    for (i=1;i<=dp[n-1][m-1];i++)
        printf("%d ",p[i]);

    return 0;

}