Se dau n piese de domino.
Fiecare piesa poate fi rotita cu 180 de grade.
Sa se determine subsirul de piese de lungime maxima astfel incat oricare 2 piese alaturate in subsir sa aiba un numar in comun.
Exemplu:
v.first: 5 1 2 3 1 6 5 5 2 1 5 5 3
v.second: 6 1 5 2 5 4 1 3 1 4 5 2 3
Algoritm:
#include <fstream.h>
#include <iostream.h>
typedef struct { int first, sec; } PIESA;
PIESA v[100];
int n, d[2][100], poz[2][100];
void citire()
{
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 i, k ,p, aux, max=0;
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<<endl;
if(k==0) { cout<<v[p].first<<” “<<v[p].sec<<endl; aux=v[p].sec;}
else { cout<<v[p].sec<<” “<<v[p].first<<endl; aux=v[p].first;}
p=poz[k][p];
while(p>0)
{ if(aux==v[p].first)
{ cout<<v[p].first<<” “<<v[p].sec<<endl; aux=v[p].sec; k=0;}
else { cout<<v[p].sec<<” “<<v[p].first<<endl; aux=v[p].first; k=1;}
p=poz[k][p];
}
}
int main ()
{
citire();
dinamica();
afisare();
return 0;
}
