Cod sursa(job #260756)

Utilizator alex@ndraAlexandra alex@ndra Data 17 februarie 2009 15:26:54
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
using namespace std;

int a[1024], b[1024], c[1024][1024],s[1024];
int max(int a, int b)
{
    if(a>b)
      return a;
   else return b;
}

int main()
{
    int m,k=0, n, i, j;
    
    ifstream f("cmlsc.in");
      f>>m>>n;
    for(i=1;i<=m;i++)
     f>>a[i];
    for(i=1;i<=n;i++)
     f>>b[i];
   f.close();
   
   for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
       if(a[i]==b[j])
         c[i][j]=c[i-1][j-1]+1; 
       else
          c[i][j]=max(c[i-1][j],c[i][j-1]);
   
  ofstream g("cmlsc.out");
   
    g<<c[m][n]<<endl;
    i=m;j=n;k=c[m][n];
while(k>0)
{
    if(c[i][j]=c[i-1][j-1]+1)
        {s[k]=a[i];k--;i=i-1;j=j-1;}
    else if(c[i-1][j]>c[i][j-1])
                i=i-1;
     else j=j-1;
     }
   for(i=1;i<=c[m][n];i++)
     g<<s[i]<<" ";
       
                    

     g.close();
     return 0;
     }