1. 从“画廊”到“动态规划”一场算法竞赛的实战复盘最近在整理过往的算法竞赛笔记翻到了“蓝桥杯国赛-画廊”这道题。这道题在当年的赛场上可以说是一道典型的分水岭题目它不像那些一眼就能看出是DFS或者BFS的搜索题也不像纯数学推导题那么抽象。它披着一层“画廊”的生活化外衣内核却是一个经典的动态规划问题考察的是选手对状态定义、状态转移以及边界条件处理的综合能力。很多同学在赛场上看到题目描述里“画廊”、“画作”、“走廊”这些词可能会先入为主地往图论或者模拟的方向去想结果浪费了大量时间。今天我就来彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及我在实战和后续教学中总结出的那些容易踩坑的细节。这道题的核心场景可以抽象为你有一条长长的走廊画廊走廊两侧的墙壁上挂着若干幅画。你从走廊的一端出发需要观赏所有的画但观赏每一幅画都需要你走到该画的正前方即到达画所在的坐标点。由于画挂在两侧你需要在走廊中左右移动。最终目标是找到一条路径让你从起点出发观赏完所有画并到达走廊的另一端或某个指定终点使得总移动距离最短。这本质上是一个顺序访问一系列特定点画作位置的最短路径问题并且这些点带有“左侧”或“右侧”的属性约束。2. 问题本质抽象与状态定义的艺术面对任何动态规划问题第一步也是最关键的一步就是抛开题目描述的具体情境进行高度抽象并定义出能够完整描述“当前局面”的状态。对于“画廊”问题我们逐一分析。2.1 关键元素提取首先我们需要从题目中提取出所有的不变量和变量画廊长度L这是一个常量决定了坐标范围比如从0到L。画作数量N需要观赏的画的总数记为N。画作位置每幅画有两个属性。一是它的坐标x0 x L表示它在走廊长度方向上的位置。二是它的侧边s通常用0表示左侧1表示右侧表示它挂在左边墙还是右边墙。我们假设走廊宽度忽略不计或者宽度是固定的那么从走廊中心线走到左侧或右侧观赏画作的距离是一个固定值比如d。为了简化我们可以先考虑这个固定距离最后再纳入计算甚至有时题目会假设人就在走廊中心线上移动观赏画作只是“瞬间切换”到该侧不占距离。这一点需要仔细审题。人的状态人在任意时刻有两个核心属性。一是当前所在的长度坐标x。二是当前面朝的侧边在左侧墙边还是右侧墙边。因为如果你刚看完左侧的一幅画你下一时刻可能还在左侧也可能需要走到右侧去看画。2.2 状态定义决策最直接的想法是定义状态dp[i][x][s]表示已经观赏了前i幅画当前人位于坐标x、侧边s时所花费的最小距离。但是这个状态空间太大了i最多为Nx是连续值0到Ls为2。这几乎无法处理。这就需要我们洞察问题的一个关键性质最优路径下在观赏完第i幅画后人一定恰好位于第i幅画的位置坐标和侧边。为什么因为如果你观赏完一幅画后没有停在那幅画的位置而是走到了另一个点那么这段“多余”的移动在后续规划中一定是浪费的你可以选择在观赏完那幅画后直接停在画的位置为后续移动提供一个更优的起点。这是一个非常重要的“最优子结构”体现。因此我们可以大大简化状态定义。我们只关心在观赏完某幅画后人所处的位置。那么状态可以定义为dp[i][s]表示观赏完前i幅画并且此时人位于第i幅画所在侧边s注意这里s必须与第i幅画的侧边一致时所花费的最小总距离。 这里有一个关键点状态中的s不是独立变量它必须等于第i幅画的实际侧边side[i]。所以更准确地说dp[i]其实只有一个有效值对应s side[i]。但为了思维清晰和转移方便我们依然保留这个维度对于无效的s ! side[i]我们可以将其值设为无穷大。然而这样定义还不够因为第i幅画有一个具体的坐标pos[i]。dp[i][s]隐含了人当前就在(pos[i], side[i])这个点上。那么状态转移时我们从“观赏完第i-1幅画”到“观赏完第i幅画”就需要计算从第i-1幅画的位置(pos[i-1], side[i-1])移动到第i幅画的位置(pos[i], side[i])的距离。但这里有一个陷阱在移动过程中人是否需要切换侧边切换侧边是否会产生额外距离2.3 距离计算模型这是本题的第二个核心点也最容易出错。我们需要建立一个清晰的距离计算模型。假设画廊长度方向为X轴范围[0, L]。左侧墙的坐标设为 (x, 0)右侧墙的坐标设为 (x, 1)。走廊的“宽度”即从中心线到一侧墙的距离为 W可能为0即忽略宽度。那么从点(x1, s1)移动到点(x2, s2)的距离并不是简单的|x1 - x2|。因为如果s1 ! s2你需要从一侧墙移动到另一侧墙。最简单的曼哈顿距离模型是先沿着走廊走到目标点的正对面即从(x1, s1)走到(x2, s1)然后再横向穿过走廊从(x2, s1)走到(x2, s2)。因此距离为distance |x1 - x2| (s1 s2 ? 0 : W)这里W是穿越走廊的宽度。如果题目假设人就在中心线上移动观赏画作是“瞬间”的那么W可能就是0。务必根据题目描述确定W的值。很多同学忘记加W导致结果错误。3. 动态规划转移方程推导与初始化基于以上的状态定义和距离模型我们来推导状态转移方程。我们定义pos[i]: 第i幅画的X坐标注意题目给出的画作可能是乱序的我们通常需要先按照X坐标从小到大排序因为最优解中观赏画的顺序一定和X坐标顺序相关吗不一定但排序后可以简化决策这是一个需要证明的贪心性质。在经典“画廊”问题中通常规定必须按画作顺序观赏或者画作位置已经给定顺序。我们这里假设画作列表已经按某种顺序给出我们只能按这个顺序观赏。这是题目约束非常重要。side[i]: 第i幅画的侧边0左1右。dp[i][0]: 观赏完前i幅画且人停在左侧即第i幅画必须在左侧的最小距离。dp[i][1]: 观赏完前i幅画且人停在右侧即第i幅画必须在右侧的最小距离。3.1 状态转移如何计算dp[i][s]要观赏完前i幅画并停在侧边s意味着第i幅画就在侧边s上。那么在观赏第i幅画之前的状态是已经观赏完前i-1幅画并停在某个位置。这个位置就是第i-1幅画的位置其侧边是side[i-1]。因此我们从dp[i-1][0]和dp[i-1][1]都有可能转移到dp[i][s]但前提是转移是可行的并且我们要选择代价最小的那个。转移路径从(pos[i-1], side[i-1])移动到(pos[i], side[i])。 转移代价cost |pos[i-1] - pos[i]| (side[i-1] side[i] ? 0 : W)因此状态转移方程为dp[i][side[i]] min( dp[i-1][0] cost_from_0, dp[i-1][1] cost_from_1 )其中cost_from_0 |pos[i-1] - pos[i]| (0 side[i] ? 0 : W)cost_from_1 |pos[i-1] - pos[i]| (1 side[i] ? 0 : W)注意dp[i][s]只有当s side[i]时才有意义。对于s ! side[i]我们可以将其值保持为无穷大INF表示不可达状态。3.2 边界条件初始化初始化是动态规划正确性的基石。对于第一幅画i1我们如何初始化dp[1][0]和dp[1][1] 这取决于我们的起点。题目通常规定起点在走廊的一端例如左端坐标0并且可能在中心线上也可能在某一侧。我们需要计算从起点走到第一幅画的位置并完成观赏的距离。假设起点为(start_x, start_side)。那么dp[1][side[1]] distance(start_x, start_side, pos[1], side[1])dp[1][other_side] INF因为第一幅画不在另一侧不可能观赏完第一幅画后停在另一侧例如起点在左端中心(0, 0.5)或者直接规定起点就在左侧墙(0, 0)。具体计算时起点到第一幅画的距离也要用我们定义的距离模型来计算。3.3 最终答案求解观赏完所有N幅画后题目可能要求走到终点如走廊右端(L, 0)或(L, 1)或中心。那么最终答案就不是简单的min(dp[N][0], dp[N][1])。我们需要从最后一个状态观赏完第N幅画停在(pos[N], side[N])出发再走到终点。 因此最终答案为ans min( dp[N][0] distance(pos[N], 0, end_x, end_side), dp[N][1] distance(pos[N], 1, end_x, end_side) )同样这里的distance要用我们定义的模型。如果终点和起点一样有特定位置务必在初始化和最终答案计算中保持一致。4. 算法实现细节与代码剖析理论清晰后我们来看代码实现。这里我用C为例因为蓝桥杯常用C。4.1 数据结构定义首先定义画作结构体并处理输入。#include iostream #include algorithm #include cmath #include cstring using namespace std; const int MAXN 1005; // 假设画作最多1000幅 const double INF 1e18; struct Painting { int x; // 画作的X坐标 int side; // 画作所在侧0左1右 } paintings[MAXN]; int L, W, N; // 画廊长度走廊半宽或宽度画作数量 double dp[MAXN][2]; // dp[i][0/1]注意距离可能是浮点数如果坐标是整数且W是整数距离也是整数。但用double更保险。dp数组也相应用double。4.2 距离计算函数实现距离计算函数确保逻辑一致。double calcDist(int x1, int s1, int x2, int s2) { return abs(x1 - x2) (s1 s2 ? 0 : W); }4.3 核心DP过程假设起点在左侧墙的起点处(0, 0)终点在右侧墙的终点处(L, 1)。画作已经按输入顺序排列或者按x坐标排序依题目而定。int main() { // 读取输入 L, W, N cin L W N; for (int i 1; i N; i) { cin paintings[i].x paintings[i].side; } // 初始化dp数组为无穷大 for (int i 0; i N; i) { dp[i][0] dp[i][1] INF; } // 初始化从起点(0, 0)到第一幅画 dp[1][paintings[1].side] calcDist(0, 0, paintings[1].x, paintings[1].side); // 另一侧不可达已为INF // DP转移 for (int i 2; i N; i) { int cur_x paintings[i].x; int cur_side paintings[i].side; int prev_x paintings[i-1].x; int prev_side paintings[i-1].side; // 从前一个状态停在i-1幅画的左侧转移到当前状态 // 如果dp[i-1][0]是可达的 if (dp[i-1][0] INF) { double cost dp[i-1][0] calcDist(prev_x, 0, cur_x, cur_side); dp[i][cur_side] min(dp[i][cur_side], cost); } // 从前一个状态停在i-1幅画的右侧转移到当前状态 if (dp[i-1][1] INF) { double cost dp[i-1][1] calcDist(prev_x, 1, cur_x, cur_side); dp[i][cur_side] min(dp[i][cur_side], cost); } // 注意dp[i][另一侧]保持INF因为第i幅画不在那一侧 } // 计算最终答案从最后一幅画的位置走到终点(L, 1) double ans INF; if (dp[N][0] INF) { ans min(ans, dp[N][0] calcDist(paintings[N].x, 0, L, 1)); } if (dp[N][1] INF) { ans min(ans, dp[N][1] calcDist(paintings[N].x, 1, L, 1)); } // 输出答案可能需要四舍五入或保留小数 printf(%.2f\n, ans); // 示例保留两位小数 return 0; }4.4 易错点与调试技巧画作顺序这是最大的坑题目是否明确说了必须按输入顺序观赏还是可以自由选择顺序如果是自由选择那问题就变成了一个更复杂的排序问题可能需要状压DP。我遇到的经典“画廊”题通常是规定顺序的。务必仔细审题。起点终点处理起点和终点的位置和侧边一定要明确。代码中我假设起点为(0,0)终点为(L,1)。如果起点在中心那么起点到第一幅画的距离计算模型可能需要调整比如起点(0, 0.5)到画(x, s)的距离是|x-0| |0.5 - s| * W这里需要根据题目描述建立准确的数学模型。距离模型中的WW是宽度还是半宽如果人从中心线走到左侧墙距离是W那么从左侧墙到右侧墙的距离就是2W。在calcDist函数中(s1 s2 ? 0 : W)这里的W代表的是“切换一侧所需的额外距离”。如果题目说“走廊宽度为W”那么从中心到一侧是W/2从一侧到另一侧是W。你需要根据题意调整这个值。最稳妥的方法是自己画一个坐标轴明确每个点的坐标表示然后推导距离公式。浮点数精度如果坐标和W都是整数距离也是整数用int或long long更好避免浮点数误差。如果需要输出小数注意比较时用eps输出时控制格式。初始化dp[1][side[1]]的初始化一定要用起点来计算而不是0。同时将整个dp数组初始化为无穷大是非常必要的。数组下标画作从1开始编号与dp数组对齐可以避免一些边界麻烦。5. 举一反三变种与扩展思考“画廊”问题是一个非常好的动态规划教学案例。掌握了它你可以解决一类“顺序访问带属性点集的最短路径”问题。5.1 变种一画作可以按任意顺序观赏如果画作可以按任意顺序观赏目标仍是总距离最短。这就变成了一个类似“旅行商问题(TSP)”的变种。但画廊是线性的这带来了特殊性。状态可以定义为dp[mask][i][s]表示已经观赏了掩码mask代表的画作集合最后停在画作i的s侧。由于N可能不大比如N15可以用状压DP解决。状态转移时需要枚举下一个要观赏的画作j。5.2 变种二画廊有多个走廊或分支如果画廊不是简单的一条直线而是一个树形结构或分叉的走廊问题就变成了在树上的动态规划。状态可能需要记录当前在树的哪个节点、以及已经观赏了哪些画如果画挂在节点上。这会更复杂可能需要结合树形DP和状态压缩。5.3 扩展思考如何证明“最优解下看完一幅画后一定停在该画处”这是一个贪心选择性质。可以用反证法假设存在一个最优方案在看完画A后没有停在A处而是停在了另一个点P。那么从看完A到停在P这段移动对于后续观赏其他画没有任何贡献因为P不是任何画的位置。那么我们可以修改这个方案在看完A后直接停在A处后续的移动策略完全不变。这样从A到P的这段距离就被节省下来了得到了一个更优的方案与“最优”矛盾。因此原假设不成立。5.4 实战心得在竞赛中遇到此类题我的步骤通常是耐心读题三遍圈出所有约束条件起点、终点、画作顺序、移动规则、距离定义。抽象建模在草稿纸上画出坐标系用点表示画和起终点明确距离计算规则。定义状态思考什么信息能唯一确定一个“局面”。优先考虑“完成部分任务后停在哪里”。推导转移写出从状态A到状态B所需的代价。处理边界仔细思考初始状态什么都没做时在哪里和最终状态所有任务完成后是否需要去终点。代码实现注意数据类型、初始化、循环顺序和下标。测试验证用简单的样例测试比如只有1幅画、2幅画在同侧/异侧的情况手动计算验证。这道“画廊”题看似简单实则涵盖了动态规划思想的精髓最优子结构、状态定义、状态转移、边界处理。它提醒我们面对复杂问题时通过抽象抓住本质定义出简洁而强大的状态往往是解题的关键。希望这篇详细的拆解能帮助你不仅搞定这一道题更能掌握解决一类问题的方法。在算法学习的路上这种举一反三、深度思考的能力远比AC一道题更重要。