题解：骰子叠放游戏 - 最大侧面和问题

解题思路

本题需要将多个骰子按照特定规则叠放，使得其中一个侧面的数字之和最大化。关键点在于：

1. 骰子连接规则：上方骰子的底面数字必须等于下方骰子的顶面数字
2. 旋转自由度：在固定顶面和底面后，骰子可以旋转$90°$、$180°$或$270°$
3. 目标：最大化四个侧面中某一个面的数字之和

采用动态规划方法，状态设计为$dp[state][i][j]$，表示在状态$state$下，第$i$个骰子$j$面朝上时的最大侧面和。

算法分析

1. 状态表示：

   • 使用位掩码$state$表示已使用的骰子集合
   • $i$表示当前处理的骰子编号
   • $j$表示当前骰子的顶面

2. 状态转移：

   • 对于每个状态，尝试添加一个新骰子
   • 检查新骰子的底面数字是否匹配已有骰子的顶面数字
   • 更新最大侧面和

3. 复杂度分析：

   • 状态数：$O(2^n \times n \times 6)$
   • 对于$n \leq 10$，总状态数为$1024 \times 10 \times 6 = 61440$，可接受

4. 优化点：

   • 预处理每个骰子各面朝上时的最大侧面和
   • 使用位运算高效处理状态

实现步骤

1. 输入处理：

   • 读取骰子数量$n$和每个骰子的面数字

2. 预处理：

   • 计算每个骰子各面朝上时的最大侧面和$maxs[i][j]$

3. 动态规划：

   • 初始化单骰子状态
   • 状态转移：尝试添加新骰子并更新最大值

4. 结果输出：

   • 遍历所有最终状态，找出最大侧面和

C++代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

// 全局变量定义
int dice[10][6];      // 存储每个骰子的6个面数字，最多10个骰子
int maxs[10][6];      // 存储每个骰子各面朝上时的最大侧面和
int sd[] = {5, 3, 4, 1, 2, 0}; // 相对面关系数组，sd[i]表示第i面的对面索引
int dp[1024][10][6];  // 动态规划状态数组，1024对应最多10个骰子的状态(2^10)

int main() {
    ios::sync_with_stdio(false);  // 关闭同步，提高输入输出速度
    cin.tie(0);cout.tie(0);      // 解除cin和cout的绑定
    
    int t;  // 测试用例数量
    cin >> t;
    while (t--) {
        int n;  // 当前测试用例的骰子数量
        cin >> n;
        
        // 初始化数组
        memset(dice, 0, sizeof(dice));
        memset(maxs, 0, sizeof(maxs));
        memset(dp, 0, sizeof(dp));
        
        // 输入骰子数据
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < 6; ++j)
                cin >> dice[i][j];
        
        // 预处理maxs数组：计算每个骰子各面朝上时的最大侧面和
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 6; ++j) {
                // 遍历所有侧面(非当前面和对面)
                for (int k = 0; k < 6; ++k) {
                    if (k != j && k != sd[j]) {
                        maxs[i][j] = max(maxs[i][j], dice[i][k]);
                    }
                }
            }
        }
        
        // 动态规划求解
        for (int state = 0; state < (1 << n); ++state) {  // 遍历所有骰子组合状态
            for (int i = 0; i < n; ++i) {  // 遍历所有骰子
                if (state & (1 << i)) {    // 如果当前状态包含第i个骰子
                    if (state == (1 << i)) {
                        // 初始状态：只有一个骰子时，直接取各面朝上时的最大侧面和
                        for (int j = 0; j < 6; ++j) {
                            dp[state][i][j] = maxs[i][j];
                        }
                    } else {
                        // 状态转移：尝试将当前骰子i添加到已有状态中
                        for (int j = 0; j < n; ++j) {  // 遍历可能的上一个骰子
                            if ((state & (1 << j)) && i != j) {  // 确保j在状态中且不是i
                                for (int k1 = 0; k1 < 6; ++k1) {  // 当前骰子的面
                                    for (int k2 = 0; k2 < 6; ++k2) {  // 上一个骰子的面
                                        // 检查当前骰子的底面是否等于上一个骰子的顶面
                                        if (dice[j][k2] == dice[i][sd[k1]] && dp[state ^ (1 << i)][j][k2]) {
                                            // 状态转移方程
                                            dp[state][i][k1] = max(dp[state][i][k1], 
                                                dp[state ^ (1 << i)][j][k2] + maxs[i][k1]);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        
        // 输出结果：在所有骰子都使用且任意顶面情况下的最大值
        int result = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 6; ++j) {
                result = max(result, dp[(1 << n) - 1][i][j]);
            }
        }
        cout << result << endl;
    }
    return 0;
}