Dice Stacking
【題目概述】羅骰子游戲，N（1<=N<=10）個(gè)骰子，每個(gè)骰子有六個(gè)編號(hào)為0~5的面，現(xiàn)在要求把骰子羅成一摞，且要求兩個(gè)骰子重疊的面的編號(hào)相等，求羅成的長(zhǎng)方體四個(gè)側(cè)面中最大面積的側(cè)面的面子。
【題目分析】將骰子羅列，求最大的側(cè)面，還要求相鄰兩個(gè)骰子接觸面編號(hào)相等？！該如何解決呢？看圖，先來(lái)解決相鄰的兩個(gè)面編號(hào)相等的問(wèn)題！有圖得到 因此，可以很容易的判斷一個(gè)面的對(duì)立面！第一個(gè)問(wèn)題解決。
題目中給出了這個(gè)條件是狠重要就是，就是一個(gè)骰子可以左右轉(zhuǎn)動(dòng)，這提示我們水平的四個(gè)面中編號(hào)最大的面總是可以轉(zhuǎn)到一個(gè)面上的。由此，我們可以確定那個(gè)面和其余骰子接觸的時(shí)候，確定這個(gè)骰子提供的最大的面積。
確定這兩個(gè)起初看是不確定的問(wèn)題，下面的算法就是比較通俗的了。
設(shè) 表示最大值，其中，i為已放入的骰子，第j個(gè)骰子的第k個(gè)面朝上。則
若只放一個(gè)篩子， , 其中b[i][j]表示第i個(gè)骰子的第j個(gè)面向上放置貢獻(xiàn)的最大值，可以預(yù)處理的時(shí)候求出。
對(duì)于已放置的骰子，可以轉(zhuǎn)移到為放置的上面，所以，枚舉合法的狀態(tài)，然后添加骰子，同時(shí)更新?tīng)顟B(tài)值。
【詳細(xì)代碼】下面是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;
}