题目描述考虑一个由191919个六边形格子组成的游戏棋盘如图所示。棋盘有三个主要方向从上到下垂直方向、从左上到右下对角线方向、从右上到左下对角线方向。对于每个方向棋盘可以看作一系列行分别包含3,4,5,4,33,4,5,4,33,4,5,4,3个格子。棋盘需要完全覆盖一组六边形棋子。每个棋子带有三个数字每个数字对应棋盘的一个主方向。每个方向只使用三种不同的数字。所有三个方向的数字的所有可能组合都被分配到一个棋子从而产生272727个不同的棋子。棋盘得分计算为所有151515行得分之和每个方向555行。行得分计算如下如果一行中的所有棋子在行的方向上具有相同的数字则行得分 该数字 × 该行中的棋子数量否则行得分为000注意棋子不能旋转。给定每个方向的三个数字共999个数字要求选择191919个棋子从272727个可能的棋子中选取使得棋盘得分最高。输出该最高得分。输入格式输入文件第一行包含一个整数nnn表示测试用例的数量。每个测试用例由三行组成每行包含三个整数。每行对应一个主方向的三个数字。从这些数字生成所有可能的棋子组合。输出格式对于每个测试用例输出一行Test #1、Test #2等然后一行输出给定数字的最高可能得分。每个测试用例后输出一个空行。样例输入1 9 4 3 8 5 2 7 6 1样例输出Test #1 308题目分析问题的本质这是一个组合优化问题。有191919个格子每个格子需要放置一个棋子。棋子由三个方向的数字唯一确定每个方向从三种可能数字中选择一种。因此所有可能的棋子共有3×3×3273 \times 3 \times 3 273×3×327种。棋盘的得分由151515行得分之和决定。每个方向的555行分别包含3,4,5,4,33,4,5,4,33,4,5,4,3个格子。每行的得分仅当该行所有棋子在行方向上的数字相同时才非零。目标是选择191919个棋子的放置方案使得总分最大化。关键观察观察 1每个方向的行得分是独立的吗不完全是因为每个格子同时属于三个方向每个方向各一行所以一个棋子的三个数字会同时影响三个方向的得分。观察 2由于每个方向只有333种可能的数字每行的得分只取决于该行中所有棋子在行方向上选择的数字是否一致。观察 3固定一个方向后该方向上的555行中每行需要选择一种数字333种可能之一。如果某行选择的数字一致则获得相应得分否则得分为000。观察 4棋子的数量272727是固定的但棋盘只需要191919个棋子。实际上我们可以从272727个棋子中任意选择191919个。这意味着我们可以自由决定每个格子使用什么棋子只要每个格子对应一个唯一的(d1,d2,d3)(d_1, d_2, d_3)(d1​,d2​,d3​)三元组其中did_idi​是第iii个方向的数字。观察 5棋盘的结构具有对称性。每个方向的行长度分布为[3,4,5,4,3][3,4,5,4,3][3,4,5,4,3]。这些长度乘以对应的数字就得到该行可能的最大得分。解题思路问题简化由于每个格子必须放置一个棋子而棋子的选择是独立的我们可以把问题看作在5×35 \times 35×3的网格每个方向的行索引1∼51 \sim 51∼5和数字索引1∼31 \sim 31∼3中为每个方向分配一个数字使得总分最大化。设三个方向的数字集合分别为方向111a1a2a3a_1 a_2 a_3a1​a2​a3​排序后方向222b1b2b3b_1 b_2 b_3b1​b2​b3​方向333c1c2c3c_1 c_2 c_3c1​c2​c3​棋盘共有151515行每个方向555行。设第iii个方向第jjj行的长度为LjL_jLj​j1j 1j1L3L 3L3j2j 2j2L4L 4L4j3j 3j3L5L 5L5j4j 4j4L4L 4L4j5j 5j5L3L 3L3得分公式如果方向111的第jjj行选择了数字ata_tat​则该行得分为Lj×atL_j \times a_tLj​×at​。如果该行数字不一致得分为000。但这里有一个关键约束每个格子上的三个数字必须一致。也就是说如果方向111的一行选择了某个数字那么该行每个格子还对应方向222和方向333的某个数字。这些选择必须相互兼容——每个格子只能有一个数字组合。更深入的观察经过分析通过枚举或推理可以发现最优解的结构是存在一个方向其所有行都选择相同的数字而对于另外两个方向它们选择数字的方式是固定的。实际上代码中使用的优化方法表明对于每个方向当它作为“主方向”时其他两个方向的数字选择模式是固定的。具体来说如果方向111是主方向所有行选择相同的数字那么方向222和方向333的行分配数字的方式是确定的由模式{5,6,8}和{5,7,7}给出。这些数字5,6,8,5,7,75,6,8,5,7,75,6,8,5,7,7实际上代表了每个方向行长度与数字索引的乘积组合。算法对于每个测试用例读取三个方向的三个数字每个方向排序升序对于k0,1,2k 0,1,2k0,1,2将方向kkk作为主方向计算得分主方向的所有行选择最大数字因为数字越大得分越高实际上需要选择排序后最大的数字对于另外两个方向使用固定模式分配取三种情况的最大值作为答案算法复杂度分析时间复杂度每个测试用例O(1)O(1)O(1)总复杂度O(n)O(n)O(n)空间复杂度常数空间O(1)O(1)O(1)正确性说明代码中使用了一个预计算的模式pieces[2][3] {{5, 6, 8}, {5, 7, 7}}。这个模式来源于对棋盘结构的分析。棋盘每个方向的行长度分布为3,4,5,4,33,4,5,4,33,4,5,4,3。当主方向的所有行选择相同的数字时另外两个方向的得分可以通过固定分配计算。具体计算方式pieces[0][j]和pieces[1][j]表示对于另外两个方向的数字索引jjjj0,1,2j0,1,2j0,1,2应该乘以的行长度这些数值5,6,8,5,7,75,6,8,5,7,75,6,8,5,7,7来源于5325 32532实际上555对应323232模式666对应424242模式888对应535353模式等通过枚举所有可能的分配方案可以验证这种简化是正确的。参考代码// Hexagon// UVa ID: 317// Verdict: Accepted// Submission Date: 2016-11-23// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);// 预计算的系数模式// 当某个方向作为主方向时另外两个方向的行长度分配系数intpieces[2][3]{{5,6,8},{5,7,7}};intnumber[3][3];// 存储三个方向的三组数字intcases;cincases;for(intc1;ccases;c){coutTest #c\n;// 读取每个方向的三个数字并排序for(inti0;i3;i){for(intj0;j3;j)cinnumber[i][j];sort(number[i],number[i]3);}// 尝试将每个方向作为主方向intmax_scores0;for(intk0;k3;k){intscores0;for(inti0;i3;i)// 遍历三个方向{for(intj0;j3;j)// 遍历该方向的三个数字{// 如果当前方向是主方向 (i k)使用系数 pieces[0][j]// 否则使用 pieces[1][j]scoresnumber[i][j]*pieces[(ik?0:1)][j];}}max_scoresmax(max_scores,scores);}coutmax_scores\n\n;}return0;}总结本题的核心在于问题建模将191919个格子的棋子放置抽象为151515行的得分计算对称性利用棋盘结构具有对称性最优解可以通过枚举主方向得到系数预计算通过分析棋盘的行长度分布预计算得分系数关键点回顾知识点说明棋盘结构三个方向每个方向555行长度3,4,5,4,33,4,5,4,33,4,5,4,3棋子种类3×3×3273 \times 3 \times 3 273×3×327种行得分行内数字一致时 数字 × 行长度主方向一个方向的所有行选择相同数字系数模式预计算的行长度分配系数解题启示这类问题通常可以通过以下方式解决分析问题的数学结构识别对称性和化简枚举少量可能性使用预计算优化虽然代码看起来很短但背后是对棋盘结构的深入分析。这种“先分析再编码”的思路值得学习。