S表示已用骰子的集合。
dp[S][i][j]表示在当前集合下，最上面那个骰子为 i ，底面编号为 j 时所能得到的最大和, max[i][j] 表示骰子 i 以 j 为底时侧面的最大值，dice[i][j]表示 i 骰子 j 面的编号。
dp[S][i][j] = max{ dp[ S ^ ( 1 << i ) ][k][m]+max[i][j] };
k∈(S ^ ( 1 << i ) ), dice[k][5 - m]==dice[i][j]。
为了方便判断相对的面，存储时处理一下，使得相对的面存储在编号加和为5的位置中。
即如果 a, b 面相对，则 a + b = 5
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 int N; 9 int dice[12][6]; 10 int ans; 11 int dp[ 1 << 11 ][12][6]; 12 bool vis[ 1 << 11 ][12][6]; 13 14 int DFS( int S, int j, int botm ) 15 { 16 bool& flag = vis[S][j][botm]; 17 int& res = dp[S][j][botm]; 18 19 if ( flag ) return res; 20 21 res = -(1 << 30); 22 for ( int k = 0; k < N; ++k ) 23 if ( k != j && ( S & ( 1 << k ) ) ) 24 { 25 for ( int m = 0; m < 6; ++m ) 26 { 27 //printf("dice[%d][%d]=%d dice[%d][%d]=%d\n", k, m, dice[k][m], j, botm, dice[j][botm] ); 28 if ( dice[k][m] == dice[j][botm] ) 29 { 30 int maxi = 0; 31 for ( int kk = 0; kk < 6; ++kk ) 32 if ( kk != botm && kk + botm != 5 ) 33 maxi = max( maxi, dice[j][kk] ); 34 //printf("maxi=%d\n", maxi); 35 //printf( "dp[%d][%d][%d] = %d\n", S, j, botm, res ); 36 res = max( res, DFS( S ^ ( 1 << j ), k, 5 - m ) + maxi ); 37 //printf( "**dp[%d][%d][%d] = %d\n", S, j, botm, res ); 38 //printf("res=%d\n", res); 39 } 40 } 41 } 42 43 // printf( "dp[%d][%d][%d] = %d\n\n", S, j, botm, res ); 44 45 flag = true; 46 47 return res; 48 } 49 50 void init() 51 { 52 for ( int i = 0; i < N; ++i ) 53 { 54 for ( int j = 0; j < 6; ++j ) 55 { 56 int maxi = 0; 57 for ( int m = 0; m < 6; ++m ) 58 if ( m != j && j + m != 5 ) maxi = max( maxi, dice[i][m] ); 59 60 dp[ 1 << i ][i][j] = maxi; 61 vis[ 1 << i ][i][j] = true; 62 } 63 } 64 return; 65 } 66 67 68 int main() 69 { 70 //freopen("s.out", "w", stdout ); 71 int T; 72 scanf( "%d", &T ); 73 while ( T-- ) 74 { 75 scanf( "%d", &N ); 76 for ( int k = 0; k < N; ++k ) 77 { 78 for ( int i = 0; i < 6; ++i ) 79 scanf( "%d", &dice[k][i] ); 80 81 int tp = dice[k][3]; 82 dice[k][3] = dice[k][4]; 83 dice[k][4] = tp; 84 } 85 86 ans = 0; 87 memset( vis, false, sizeof(vis) ); 88 memset( dp, 0, sizeof(dp) ); 89 90 init(); 91 92 for ( int i = 0; i < N; ++i ) 93 for ( int j = 0; j < 6; ++j ) 94 { 95 DFS( ( 1 << N ) - 1, i, j ); 96 ans = max( ans, dp[ (1 << N) - 1 ][i][j] ); 97 } 98 99 printf( "%d\n", ans );100 }101 return 0;102 }
吐槽：
一开始看 n<= 10 直接当成搜索来搞了……于是理所应当的TLE……
后来明白是个跟集合有关的DP，用的记忆化搜索，结果各种细节出错……初始化边界错，判断条件错，改了一个半小时才过，我勒个去去去去……