MCARDS - Card Sorting
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
struct st_card
{
int color,value;
};
st_card A[412];
int main()
{
//freopen("MCARDS.in","r",stdin);
int colors,numbers,cards,a[6],b[6],giaithua[6],the,chia,f[414],x[414],gan;
scanf("%d %d",&colors,&numbers);
cards = colors*numbers;
for(int i = 1;i<= cards;i++)
scanf("%d %d",&A[i].color,&A[i].value);
giaithua[0] = 1;
for(int i = 1;i<=colors;i++)
giaithua[i] = giaithua[i-1]*i;
int KQ = cards;
for(int ii = 0;ii < giaithua[colors];ii++)
{
//printf("1");
the = ii;for(int i = 1; i <= colors ;i++) b[i] = i;
for(int i = 1;i<=colors;i++)
{
chia = the/giaithua[colors-i];
a[i] = b[chia+1];
for(int j = chia+1;j<=colors-i;j++)
b[j] = b[j+1];
the = the%giaithua[colors-i];
}
for(int i = 1;i<=cards;i++) x[i] = a[A[i].color]*numbers+A[i].value;
for(int i = 1;i<=cards;i++)
{
gan = 1;
for(int j = 1;j<i;j++)
if(x[j]<x[i] && gan<f[j]+1)
gan = f[j]+1;
f[i] = gan;
if(cards - gan <KQ)
KQ = cards-gan;
}
}
printf("%d",KQ);
//getch();
}