*Enunt:*

Se dau n piese de domino.Fiecare piesa poate fi rotita cu 180°.

*Se cere:*

Determinati subsirul de piese de lungime maxima astfel incat oricare 2 piese alaturate sa aiba un numar in comun.

Exemplu:

vp.first: 5 1 2 3 1 6 5 5 2 1 5 5 3

vp.second:6 1 5 2 5 4 1 3 1 4 5 2 3

v.0:6 5 5 3 4 2 3 2 2 1 2 1 1

v.1:6 5 5 4 4 1 3 3 2 1 2 1 1

v.next.0:6 5 5 9 7 10 9 13 10 0 12 0 0

v.next.1:3 5 4 8 7 0 8 11 12 0 12 0 0

Rezolvare:

#include<iostream.h>

#include<fstream.h>

typedef struct {int first,sec;}PIESA;

PIESA v[100];

int d[2][100],poz[2][100],n;

void citire()

{

n=0;

ifstream f(“domino.in”);

while(!f.eof())

{

f>>v[++n].first>>v[n].sec;

}

f.close();

}

void dinamica()

{

int i,j,max0,max1,p0,p1;

d[0][n]=d[1][n]=1;

poz[0][n]=poz[1][n]=0;

for(i=n-1;i>=1;i–)

{

max0=max1=0;

p0=p1=0;

for(j=i+1;j<=n;j++)

{

if(v[i].sec==v[j].first&&d[0][j]>max0)

{

max0=d[0][j];p0=j;}

if(v[i].sec==v[j].sec&&d[1][j]>max0)

{

max0=d[1][j];p0=j;}

if(v[i].first==v[j].sec&&d[1][j]>max1)

{

max1=d[1][j];p1=j;}

if(v[i].first==v[j].first&&d[0][j]>max1)

{

max1=d[0][j];p1=j;}

}

d[0][i]=max0+1;

d[1][i]=max1+1;

poz[0][i]=p0;

poz[1][i]=p1;

}

}

void afisare()

{

int k,p,aux,i,max;

for(i=1;i<=n;i++)

{

if(d[0][i]>max){max=d[0][i];k=0;p=1;}

if(d[1][i]>max){max=d[1][i];k=1;p=i;}

}

if(k==0)

{

cout<<v[p].first<<” “<<v[p].sec;

aux=v[p].sec;}

else {cout<<v[p].sec<<” “<<v[p].first;

aux=v[p].first;}

p=poz[k][p];

while(p>0)

{

if(aux==v[p].first){cout<<v[p].first<<” “<<v[p].sec;k=0;aux=v[p].sec;}

else{cout<<v[p].sec<<” “<<v[p].first;k=1;aux=v[p].first;

}

p=poz[k][p];

}

}

int main()

{

int max=0,i,k,p;

citire();

dinamica();

for(i=1;i<=n;i++)

{

if(d[0][i]>max){max=d[0][i];k=0;p=i;}

if(d[1][i]>max){max=d[1][i];k=1;p=i;}

}

cout<<max;

return 0;

}