#include <stdio.h>
#include <string.h>

int f[1<<10][10][6],se[10][6];
//int g[1<<10][10][6];
int main ()
{
	int t,c,n,i,j,k,r,w,max,di,cnt,ga;
	scanf ("%d",&t);
	for (c=1;c<=t;c++)
	{
		memset (f,0,sizeof (f));
//		memset (g,-1,sizeof (g));
		memset (se,0,sizeof (se));
		scanf ("%d",&n);
		for (i=0;i<n;i++)
			for (j=0;j<6;j++)
			{
				scanf ("%d",&se[i][j]);
			}
		for (i=0;i<n;i++)
			for (j=0;j<6;j++)
			{
				for (k=0;k<6;k++)
				{
					if (se[i][k]==j+1)
					{
						ga=k;
						if (k==0) di=5;
						if (k==1) di=3;
						if (k==2) di=4;
						if (k==3) di=1;
						if (k==4) di=2;
						if (k==5) di=0;
						break;
					}
				}
				for (max=0,k=0;k<6;k++)
				{
					if (k==di || k==ga) continue;
					if (se[i][k]>max) max=se[i][k];
				}
				f[1<<i][i][se[i][di]-1]=max;
			}
		cnt=0;
		for (i=0;i<(1<<n);i++)
		{
			for (j=0;j<n;j++)
			{	
				if ((i+(1<<j))>(1<<n)-1) break;			
				if ((i>>j)%2==1) continue;
				for (k=0;k<n;k++)
				{
					if ((i>>k)%2==0 || k==j) continue;
					for (r=0;r<6;r++)
					{
						for (w=0;w<6;w++)
						{
							if (se[j][w]==r+1)
							{
								ga=w;
								if (w==0) di=5;
								if (w==1) di=3;
								if (w==2) di=4;
								if (w==3) di=1;
								if (w==4) di=2;
								if (w==5) di=0;
								break;
							}
						}
						for (max=0,w=0;w<6;w++)
						{
							if (w!=di && w!=ga && max<se[j][w])
							max=se[j][w]; 
						}
						if (f[i+(1<<j)][j][se[j][di]-1]<f[i][k][r]+max)
						{
							f[i+(1<<j)][j][se[j][di]-1]=f[i][k][r]+max;
//							g[i+(1<<j)][j][di]=g[i+(1<<j)][k][ga];
						}
						if (f[i+(1<<j)][j][se[j][di]-1]>cnt)
							cnt=f[i+(1<<j)][j][se[j][di]-1];
					}
				}
			}
		}
		/*
		for (i=0;i<(1<<n);i++)
		{
			for (j=0;j<n;j++)
			{
				for (k=0;k<6;k++)
					printf ("%d ",f[i][j][k]);
				printf ("\n");
			}
			printf ("\n");
		}*/
			
		max=0;
		for (i=0;i<n;i++)
			for (j=0;j<6;j++)
				if (f[(1<<n)-1][i][j]>max)
				{
					max=f[(1<<n)-1][i][j];
				}
		if (max!=0)
		printf ("%d\n",max);
		else printf ("0\n");
	}	
	return 0;
}

• 这道题为什么会有色子不能全部堆在一起的情况出现？ (2366) washington 2005-09-08 10:13:01
  • Re:这道题为什么会有色子不能全部堆在一起的情况出现？ (36) victorcheng 2005-09-11 20:22:21
    • 这色子还真奇怪:( (48) number 2005-09-11 20:47:54