infooo domino

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;
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s