1. 项目概述与问题拆解最近在带学生刷信奥信息学奥林匹克的题目碰到一道挺有意思的DP动态规划题——P1282 多米诺骨牌。这道题在洛谷和不少OJ上都被标记为“普及/提高”的难度核心是考察对背包DP思想的灵活运用以及如何处理“差值最小化”这个目标。很多初学者一看到“最小差值”、“上下点数”这些描述就容易发懵感觉无从下手。其实只要把问题模型转化对了代码写起来并不复杂。今天我就结合自己带学生调试的经验把这道题的解题思路、核心实现细节以及几个容易踩的坑从头到尾捋一遍。无论你是正在备赛的信奥选手还是想巩固DP基础的C学习者这篇都能给你提供一个可以直接“抄作业”的清晰路径。简单来说题目给你一堆多米诺骨牌每张牌上下两部分各有一个点数。你可以通过旋转任意张牌来交换其上下点数。我们的目标是通过旋转一些牌使得所有牌“上半部分点数之和”与“下半部分点数之和”的差值的绝对值最小。在差值最小的前提下还要求旋转的次数尽可能少。这听起来有点像在做一个“平衡”操作我们既要让天平两端上半部分和与下半部分和尽量接近又要尽可能少地动手去翻牌子。这种带有两个优化目标最小差值、最小旋转次数的问题是DP中一个经典的变种需要一点技巧来同时处理。2. 核心思路与模型转化2.1 为什么是背包问题刚拿到题目可能第一反应是去枚举每张牌翻还是不翻。但牌数最多有1000张每张牌有两种状态原样或旋转总状态数是2的1000次方这显然是不可行的。我们必须寻找更高效的算法。这里的关键洞察在于旋转一张牌对于“上下点数总和之差”的影响是固定的。假设一张牌原来的上点数是a下点数是b。那么初始状态下这张牌对“上半部分和”的贡献是a对“下半部分和”的贡献是b其对总差的贡献是a - b如果我们定义差值为 上半部分和 - 下半部分和。当你旋转它之后上点数变成b下点数变成a其对总差的贡献就变成了b - a。那么旋转这张牌所带来的“差值变化量”是多少呢新的贡献减去旧的贡献(b - a) - (a - b) 2*(b - a)。换句话说旋转一张牌会使总差值减少2*(a - b)因为2*(b - a) -2*(a - b)。我们记每张牌的“原始差值”为diff[i] a[i] - b[i]。那么旋转第i张牌总差值就会变化-2 * diff[i]。这样一来问题就转化了我们有一个初始的总差值sum_diff sum(a[i] - b[i])。我们可以选择旋转一些牌每旋转一张牌i总差值就会增加一个值-2 * diff[i]。我们的目标是通过选择旋转哪些牌使得最终的总差值的绝对值|sum_diff sum(选择旋转的牌带来的变化)|最小。同时在绝对值最小的所有方案中选择旋转牌数最少的方案。这不就是一个选择问题吗我们有N个物品骨牌每个物品有一个“价值”即旋转它带来的差值变化change[i] -2 * diff[i]。我们可以选择拿旋转或者不拿不旋转。我们要决定拿哪些使得最终的总“价值”加上初始值后其绝对值最小。这非常类似于背包问题中“能否凑出某个总和”的模型。2.2 动态规划状态设计既然类似背包我们就可以用DP来求解。定义状态dp[i][j]。这里的i表示我们考虑前i张牌。j表示什么最直接的想法是表示“上半部分和”或者“下半部分和”但它们的范围可能很大每张牌点数1到6最多1000张牌总和可达6000二维数组开1000 * 12000在空间和时间上都是压力。回顾我们的转化我们关心的是总差值。初始总差值sum_diff的范围是[-6000, 6000]因为每张牌的diff范围是[-5, 5]。我们旋转牌带来的变化change[i]范围是[-10, 10]。经过一系列操作最终的总差值范围也大致在[-6000, 6000]之间。为了让数组下标不为负我们需要一个偏移量BASE。通常取BASE 最大可能的总差值绝对值之和这里可以取6*1000 6000或更大一些以确保安全比如BASE 6000。那么差值d对应的数组下标就是d BASE。所以我们可以定义状态dp[i][j]表示考虑前i张牌使得总差值恰好为j - BASE时所需要的最少旋转次数。注意j是数组下标对应的实际差值是j - BASE。这里有个非常重要的细节为什么是“最少旋转次数”因为我们的首要目标是差值绝对值最小次要目标是旋转次数最少。在DP过程中对于同一个差值状态可能有多种旋转组合能达到我们当然要记录旋转次数最少的那一种为后续选择最优解做准备。2.3 状态转移方程有了状态定义转移方程就清晰了。对于第i张牌我们有两种选择不旋转那么总差值的变化为0。要达到状态dp[i][j]可以从dp[i-1][j]转移过来旋转次数不变。dp[i][j] min(dp[i][j], dp[i-1][j])旋转那么总差值会增加change[i]即-2 * diff[i]。设change -2 * diff[i]。要达到状态dp[i][j]可以从dp[i-1][j - change]转移过来旋转次数加1。dp[i][j] min(dp[i][j], dp[i-1][j - change] 1)我们需要初始化DP数组。一开始没有考虑任何牌时总差值就是0旋转次数也是0。所以dp[0][BASE] 0因为实际差值0对应下标BASE。其他状态初始化为一个很大的数比如INF表示无法达到。最终我们遍历所有可能的最终差值下标j计算实际差值的绝对值abs(j - BASE)。找到所有能使dp[N][j]不为INF的j中绝对值最小的那些。然后在这些绝对值最小的j中找出dp[N][j]最小的那个即为答案最小差值以及对应的最少旋转次数。3. 代码实现与逐行解析思路清晰后我们来看C实现。我会用滚动数组优化空间因为当前状态i只依赖于前一个状态i-1。#include iostream #include cstring #include algorithm #include cmath using namespace std; const int MAXN 1005; // 最大牌数 const int MAXV 12005; // 差值范围-6000~6000加上偏移量BASE6000后下标范围0~12000 const int INF 0x3f3f3f3f; // 用一个很大的数代表“不可达” const int BASE 6000; // 偏移量使负差值也能用数组下标表示 int a[MAXN], b[MAXN]; // 存储每张牌的上下点数 int dp[2][MAXV]; // 滚动数组dp[0]和dp[1]交替使用 int main() { int n; cin n; int sum_diff 0; // 初始总差值 sum(a[i] - b[i]) for (int i 1; i n; i) { cin a[i] b[i]; sum_diff (a[i] - b[i]); } // 初始化dp数组为“不可达” memset(dp, 0x3f, sizeof(dp)); // 初始状态考虑0张牌差值为0旋转次数为0 dp[0][BASE] 0; int cur 0, nxt 1; // cur代表前一层(i-1)nxt代表当前层(i) for (int i 1; i n; i) { int diff a[i] - b[i]; int change -2 * diff; // 旋转这张牌带来的差值变化 // 初始化当前层为“不可达” memset(dp[nxt], 0x3f, sizeof(dp[nxt])); for (int j 0; j MAXV; j) { if (dp[cur][j] INF) continue; // 如果前一个状态不可达跳过 // 选择1不旋转第i张牌 dp[nxt][j] min(dp[nxt][j], dp[cur][j]); // 选择2旋转第i张牌 int new_j j change; // 旋转后差值下标的变化 // 确保新的下标在合法范围内 if (new_j 0 new_j MAXV) { dp[nxt][new_j] min(dp[nxt][new_j], dp[cur][j] 1); } } // 交换cur和nxt为下一轮做准备 swap(cur, nxt); } // 寻找答案 int min_abs_diff INF; // 最小的绝对值差值 int min_rotate INF; // 对应最小差值下的最少旋转次数 for (int j 0; j MAXV; j) { if (dp[cur][j] INF) continue; // 最终状态不可达跳过 int actual_diff j - BASE; // 实际差值 int abs_diff abs(actual_diff); if (abs_diff min_abs_diff) { // 找到了更小的绝对值差值更新答案 min_abs_diff abs_diff; min_rotate dp[cur][j]; } else if (abs_diff min_abs_diff) { // 如果绝对值差值一样取旋转次数更少的 min_rotate min(min_rotate, dp[cur][j]); } } cout min_rotate endl; return 0; }3.1 关键代码段解析常量定义MAXV 12005这是经过计算的安全值。初始差值sum_diff范围是[-6000, 6000]。每张牌旋转带来的变化change范围是[-10, 10]。最极端的情况1000张牌都朝一个方向变化总变化量是±10000。所以最终差值范围大约是[-16000, 16000]。为了保险和计算方便我们通常把BASE设为最大可能绝对值比如6000数组大小设为2*BASE 5或更大。这里12005足够覆盖2*600012000的范围并留有余量。滚动数组使用dp[2][MAXV]而不是dp[MAXN][MAXV]节省了大量空间从约1000*12000*4字节 ≈ 46MB降到约2*12000*4字节 ≈ 96KB。cur和nxt指针交替使用模拟了i-1和i两层状态。状态转移循环内层循环for (int j 0; j MAXV; j)遍历所有可能的差值状态。核心操作就是取最小值min这体现了动态规划“最优子结构”的特性当前状态的最优解由前一个状态的最优解转移而来。在旋转操作时必须检查new_j是否在数组边界内这是防止数组越界的关键。答案搜寻遍历所有最终状态dp[cur][j]cur现在是处理完所有牌后的那一层。先比较差值的绝对值abs_diff找到最小的。如果绝对值相同则比较旋转次数dp[cur][j]取更小的。4. 常见问题与调试心得这道题在实现时有几个地方特别容易出错我结合学生常犯的错误和调试经验来说说。4.1 数组越界与偏移量设置这是最经典的错误。dp数组的第二维代表的是“差值下标”其范围必须涵盖所有可能的最终差值。错误示例1只计算了初始差值sum_diff的范围[-6000,6000]于是设置BASE6000,MAXV12000。但忽略了旋转操作带来的变化。假设初始差值sum_diff -6000然后你旋转了1000张diff5的牌change -10总变化是-10000最终差值就是-16000对应的下标是-16000 6000 -10000这显然越界了。错误示例2知道要扩大范围但算错了。每张牌旋转带来的最大变化是abs(change) 10N张牌就是10*N 10000。所以最终差值范围是[sum_diff - 10000, sum_diff 10000]。sum_diff本身极值是±6000所以最终范围是[-16000, 16000]。因此BASE至少需要16000MAXV至少需要32000。为了保险和计算方便比如BASE取整很多AC代码会直接设BASE N*5或BASE 5000MAXV 2*BASE5。我上面的代码取BASE6000,MAXV12005对于洛谷的数据是足够的但更稳健的写法是BASE 5000MAXV 2*BASE 5。实操心得在信奥竞赛中对于这种带偏移量的DP我习惯开一个足够大的、固定的数组大小而不是去精确计算理论边界。例如直接定义const int M 10000;和const int BASE M;数组大小开2*M5。用空间换编码安全和思维简洁在时间限制内是完全可接受的。4.2 初始化与无穷大设置dp数组初始化必须用memset(dp, 0x3f, sizeof(dp))将其初始化为一个很大的数0x3f3f3f3f约等于1e9。这表示所有状态在开始时都是“不可达”的。然后单独将起点dp[0][BASE]设为0。滚动数组的当前层初始化在每一轮i循环开始时必须将dp[nxt]重新初始化为INF。因为dp[nxt]存储的是当前轮i的结果它必须由dp[cur]上一轮转移而来不能继承上一轮dp[nxt]的值那实际上是上上轮的结果。忘记初始化dp[nxt]是导致结果错误的常见原因。4.3 状态转移的顺序与逻辑我们的状态定义是dp[i][j]表示恰好达到差值j-BASE的最少旋转次数。因此在转移时是使用dp[i-1][...]的值来更新dp[i][...]。有些同学会混淆成“最多”或“至少”的概念。这里必须是“恰好”因为我们要精确计算最终的差值。如果定义成“不超过”那么在转移和最终答案统计上都会出问题。4.4 答案的提取最终我们是在所有i n的状态中寻找答案。注意我们寻找的是绝对值最小的差值而不是差值本身最小。所以要用abs(actual_diff)来比较。其次题目要求在最小差值的基础上找最小旋转次数。所以我们的搜索分两步第一优先级找到最小的abs_diff。第二优先级在所有能产生这个min_abs_diff的状态中找到dp[n][j]的最小值。代码中的if (abs_diff min_abs_diff)和else if (abs_diff min_abs_diff)就完美实现了这个两级比较逻辑。4.5 关于输入与点数范围题目保证点数在1到6之间所以diff的范围是[-5, 5]change的范围是[-10, 10]。这个范围不大是DP可行的前提。如果点数范围很大这种以“差值”为状态的DP可能就不适用了需要考虑其他方法。5. 算法优化与变种思考5.1 空间优化的另一种写法上面用了滚动数组。也可以只用一维数组但需要倒序枚举差值下标j。这是因为每个物品骨牌只能使用一次旋转或不旋转属于01背包。如果正序枚举一个物品可能会被重复使用相当于完全背包这不符合题意。一维DP的核心代码片段如下int dp[MAXV]; memset(dp, 0x3f, sizeof(dp)); dp[BASE] 0; // 初始状态 for (int i 1; i n; i) { int diff a[i] - b[i]; int change -2 * diff; // 倒序枚举确保每个状态只由上一轮的状态转移而来 if (change 0) { // 如果change是正数从大到小枚举防止重复使用 for (int j MAXV-1; j change; --j) { if (dp[j - change] ! INF) { dp[j] min(dp[j], dp[j - change] 1); } } } else { // 如果change是负数从小到大枚举 for (int j 0; j MAXV change; j) { if (dp[j - change] ! INF) { // 注意 j-change 等于 j abs(change) dp[j] min(dp[j], dp[j - change] 1); } } } // 不旋转的情况dp[j] min(dp[j], dp[j])相当于不变所以不用额外操作 } // 注意一维dp中“不旋转”这个选择是隐含的因为dp[j]本身会保留上一轮的值。 // 而“旋转”选择需要更新。一维写法更节省空间但逻辑上稍微绕一点需要理解倒序枚举的原理。对于初学者我建议先从二维滚动数组写起思路更直观。5.2 如果要求输出具体方案原题只要求输出最小旋转次数。但如果题目变种要求输出一种具体的旋转方案即哪些牌被旋转了我们该怎么做这就需要我们在DP的过程中记录“决策”。我们可以用另一个数组pre[i][j]来记录状态dp[i][j]是由哪个状态转移过来的以及当时是否旋转了第i张牌。定义pre[i][j] k其中k是一个编码值。我们可以约定如果dp[i][j]是从dp[i-1][j]转移而来不旋转则pre[i][j] j即前一个状态的下标。如果dp[i][j]是从dp[i-1][j-change]转移而来旋转则pre[i][j] j-change。同时我们还需要一个choice[i][j]数组来记录决策0表示不旋转1表示旋转。在求出最终答案min_abs_diff和对应的j后我们可以从in, jans_j开始根据pre和choice数组倒推回去就能知道每张牌的选择。注意事项记录方案会显著增加空间消耗从O(N*V)到O(N*V)但多了一个数组和编码复杂度。除非题目明确要求否则竞赛中通常不这么做以节省时间和避免出错。5.3 时间复杂度的考量我们的算法时间复杂度是O(N * V)其中N是牌数≤1000V是差值状态数约12000。计算量大约在10^7级别在现代计算机上完全可以在1秒内完成满足竞赛要求。6. 测试用例与调试技巧自己写几个测试用例验证程序是否正确是调试的关键。测试用例1简单情况输入 2 1 5 3 3牌1: diff 1-5 -4, change 8牌2: diff 3-3 0, change 0初始总差值 sum_diff -4 0 -4。方案旋转牌1变化8最终差值 -4 8 4绝对值4旋转1次。不旋转差值绝对值4旋转0次。但旋转后差值也是4旋转次数10所以最优是不旋转。输出应为0测试用例2需要权衡输入 3 1 2 2 1 3 4牌1: diff-1, change2牌2: diff1, change-2牌3: diff-1, change2初始 sum_diff -11-1 -1。我们可以尝试不旋转差值-1绝对值1旋转0次。旋转牌1差值-121绝对值1旋转1次。旋转牌2差值-1-2-3绝对值3旋转1次。旋转牌3差值-121绝对值1旋转1次。旋转牌1和牌3差值-1223绝对值3旋转2次。...最小绝对值是1。能达到绝对值1的方案有不旋转0次、只转牌11次、只转牌31次。取旋转次数最少的即0次。输出应为0测试用例3边界情况输入 1 6 1只有一张牌。diff5, change-10。初始 sum_diff5。不旋转差值5绝对值5旋转0次。旋转差值5-10-5绝对值5旋转1次。最小绝对值都是5取旋转次数少的0次。输出应为0调试技巧打印DP表对于小数据N3可以把整个dp数组打印出来看看每个状态的值是否如预期。重点关注BASE附近的索引。手动模拟像上面测试用例那样手动计算初始差值、每张牌的change然后模拟DP过程与程序输出对比。检查初始化确保dp[0][BASE]0其他为INF。检查数组大小这是最易出错的地方。如果程序在某个测试点发生段错误Segmentation Fault或答案错误首先怀疑MAXV是否够大。可以尝试将其调大比如翻倍再测试。使用在线判题系统的“下载测试数据”功能如果某个测试点过不了下载其输入数据在本地用调试器或打印中间变量来排查。这道“多米诺骨牌”的题目很好地融合了01背包和差值处理的思想。它不像裸的背包问题那样直接需要你先进行一步巧妙的模型转化把“旋转操作”转化为对“总差值”的调整。一旦转化成功剩下的就是标准的DP框架了。在信奥赛和算法学习中这种“转化建模”的能力往往比记忆模板更重要。多练习这类题目对提升分析问题和设计算法的能力大有裨益。