Dice Stacking
【题目概述】罗骰子游戏，N（1<=N<=10）个骰子，每个骰子有六个编号为0~5的面，现在要求把骰子罗成一摞，且要求两个骰子重叠的面的编号相等，求罗成的长方体四个侧面中最大面积的侧面的面子。
【题目分析】将骰子罗列，求最大的侧面，还要求相邻两个骰子接触面编号相等？！该如何解决呢？看图，先来解决相邻的两个面编号相等的问题！有图得到 因此，可以很容易的判断一个面的对立面！第一个问题解决。
题目中给出了这个条件是狠重要就是，就是一个骰子可以左右转动，这提示我们水平的四个面中编号最大的面总是可以转到一个面上的。由此，我们可以确定那个面和其余骰子接触的时候，确定这个骰子提供的最大的面积。
确定这两个起初看是不确定的问题，下面的算法就是比较通俗的了。
设 表示最大值，其中，i为已放入的骰子，第j个骰子的第k个面朝上。则
若只放一个筛子， , 其中b[i][j]表示第i个骰子的第j个面向上放置贡献的最大值，可以预处理的时候求出。
对于已放置的骰子，可以转移到为放置的上面，所以，枚举合法的状态，然后添加骰子，同时更新状态值。
【详细代码】下面是AC的代码。
//Name: pku_2596_Dice Stacking
#include <iostream>
using namespace std;
#define max(a, b)((a)=((a)>(b)?(a):(b)))
const int f[6]={5,4,3,2,1,0};
int a[10][10], b[10][10];
int dp[1<<10][10][6], n, ans;
int main() {
//freopen("in.in", "r", stdin);
int ca, i, j, k, p, q, t, kn;
scanf("%d", &ca);
while(ca-- && scanf("%d", &n)) {
kn = 1<<n;
memset(b, 0, sizeof(b));
for(i = 0; i < n; i++) {
for(j = 0; j < 6; j++) scanf("%d",a[i]+j);
for(j = 0; j < 6; j++)
for(k = 0; k < 6; k++) if(k!=j && k != f[j])
max(b[i][j], a[i][k]);
}
memset(dp, -1, sizeof(dp));
for(i = 0; i < n; i++)
for(j = 0; j < 6; j++) dp[1<<i][i][j] = b[i][j];
for (i = 0; i < kn; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < 6; k++) if(dp[i][j][k] != -1) {
for(p = 0; p < n; p++) if(!(i & (1<<p))) {
for (q = 0; q < 6; q++) if(a[j][k] == a[p][f[q]]) {
t = i|(1<<p);
max(dp[t][p][q], dp[i][j][k] + b[p][q]);
}//ifq
}//ifp
}//ifk
}//fj
}//fi
ans = 0;
for (i = 0; i < n; i++)
for (j = 0; j < 6; j++) max(ans, dp[kn-1][i][j]);
printf("%d\n", ans);
}
return 0;
}