12/5 - Programare dinamică/Domino & Cuburi

N piese de domino sunt aliniate pe un covor. Sa se extraga dintre acestea cat mai putine, astfel incat cele care raman sa formeze un sir care respecta regula acestui joc.

#include<iostream>
#include<iomanip>
#include<fstream>
using namespace std;
int main()
{int n,a[20],y[20],b[20],u[20],i,j,max,v,r;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
f>>a[i]>>b[i];
y[n]=1;
u[n]=-1;
for(i=n-1;i>0;i--)
{
max=0;r=-1;
for(j=i+1;j<=n;j++)
if(b[i]==a[j] && y[j]>max)
{max=y[j];
r=j;}
y[i]=max+1;
u[i]=r;
}
max=y[0];
r=0;
for(i=1;i<=n;i++)
if(y[i]>max)
{max=y[i];
r=i;}
cout<<"lungime maxima: "<<max<<endl;
cout<<"Trebuie eliminate "<<n-max<<" elemente"<<endl<<endl;
for(i=1;i<=n;i++)
cout<<setw(3)<<a[i]<<"-"<<b[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<y[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<u[i];
cout<<endl<<endl;
while(r!=-1)
{cout<<a[r]<<"-"<<b[r]<<" ";
r=u[r];
}
}

Fişier

9
1 2
2 4
2 3
2 5
4 7
3 6
4 8
7 5
5 6

Se dau n cuburi de diverse culori si laturi. Sa se afiseze cel mai lung turn care se poate construi astfel incat 2 cuburi alaturate sa aiba culori diferite si un cub sa se aseze doar pe unul mai mare decat el. 

#include<iostream>
#include<iomanip>
#include<fstream>
using namespace std;
struct cub{
int l;
char c;
}a[10];
int main()
{int n,y[20],u[20],i,j,max,v,r;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
f>>a[i].l>>a[i].c;
y[n]=1;
u[n]=-1;
for(i=n-1;i>0;i--)
{
max=0;r=-1;
for(j=i+1;j<=n;j++)
if(a[i].l>a[j].l && a[i].c!=a[j].c && y[j]>max)
{max=y[j];
r=j;}
y[i]=max+1;
u[i]=r;
}
cout<<"lungime maxima: "<<max<<endl;
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<y[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<u[i];
cout<<endl<<endl;
max=y[1];
r=1;
for(i=1;i<=n;i++)
if(y[i]>max)
{max=y[i];
r=i;}
do{cout<<a[r].l<<"-"<<a[r].c<<endl;
r=u[r];
}
while(r!=-1);
}

Fişier

9
10 R
8 N
8 R
8 A
7 N
6 M
4 R
4 M
3 V