Cod sursa(job #1076446)

Utilizator kira2071Diana C kira2071 Data 10 ianuarie 2014 10:59:23
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream>
#include <fstream>
using namespace std;
int v[257][257], nr;

ofstream g("cmlsc.out");

void reconstruire(int i,int j)
{if(i>0 && j>0)
            {if(v[0][j]==v[i][0])
                        {nr++;
                        reconstruire(i-1,j-1);
                        //cout<<v[0][j]<<" ";
                        g<<v[0][j]<<" ";

                        }
            else
                        if(v[i][j-1]>v[i-1][j])
                                    {
                                    reconstruire(i,j-1);
                                    }
                        else
                                    {
                                    reconstruire(i-1,j);
                                    }
            }
else
            g<<nr<<endl;
/*if(i>=0 && j>=0)
            reconstruire(i-1, j);*/
}


int main()
{int M,N, i,j;
ifstream f("cmlsc.in");
f>>M>>N;
for(i=1; i<=M; i++)
            f>>v[0][i];
for(i=1; i<=N; i++)
            f>>v[i][0];

for(i=1; i<=M; i++)                             //prima linie
            {if(v[0][i]==v[1][0])
                        v[1][i]=1;
            else
                        if(v[1][i-1]==1)
                                                v[1][i]=1;
                        else
                                    v[1][i]=0;
            }


for(i=1; i<=M; i++)                             //prima coloana
            {if(v[i][0]==v[0][1])
                        v[i][1]=1;
            else
                        if(v[i-1][1]==1 && i-1!=0)
                                                v[i][1]=1;
                        else
                                    v[i][1]=0;
            }



for(i=2; i<=N; i++)
            {for(j=2; j<=M; j++)

                        if(v[0][j]==v[i][0])
                                    v[i][j]=v[i-1][j-1]+1;
                        else
                                    if(v[i][j-1]>v[i-1][j])
                                                            v[i][j]=v[i][j-1];
                                    else
                                                v[i][j]=v[i-1][j];

            }




/*for(i=1; i<=N; i++)
            {for(j=1; j<=M; j++)
                        cout<<v[i][j]<<" ";
            cout<<endl;
            }
*/
reconstruire(N,M);


return 0;
}