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张牌，我们有两种选择：

1. 不旋转：那么总差值的变化为0。要达到状态dp[i][j]，可以从dp[i-1][j]转移过来，旋转次数不变。dp[i][j] = min(dp[i][j], dp[i-1][j])
2. 旋转：那么总差值会增加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，加上偏移量BASE=6000后，下标范围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 关键代码段解析

1. 常量定义：

   • MAXV = 12005：这是经过计算的安全值。初始差值sum_diff范围是[-6000, 6000]。每张牌旋转带来的变化change范围是[-10, 10]。最极端的情况，1000张牌都朝一个方向变化，总变化量是±10000。所以最终差值范围大约是[-16000, 16000]。为了保险和计算方便，我们通常把BASE设为最大可能绝对值（比如6000），数组大小设为2*BASE + 5或更大。这里12005足够覆盖2*6000=12000的范围并留有余量。

2. 滚动数组：

   • 使用dp[2][MAXV]而不是dp[MAXN][MAXV]，节省了大量空间（从约1000*12000*4字节 ≈ 46MB降到约2*12000*4字节 ≈ 96KB）。
   • cur和nxt指针交替使用，模拟了i-1和i两层状态。

3. 状态转移循环：

   • 内层循环for (int j = 0; j < MAXV; ++j)遍历所有可能的差值状态。
   • 核心操作就是取最小值（min），这体现了动态规划“最优子结构”的特性：当前状态的最优解，由前一个状态的最优解转移而来。
   • 在旋转操作时，必须检查new_j是否在数组边界内，这是防止数组越界的关键。

4. 答案搜寻：

   • 遍历所有最终状态dp[cur][j]（cur现在是处理完所有牌后的那一层）。
   • 先比较差值的绝对值abs_diff，找到最小的。
   • 如果绝对值相同，则比较旋转次数dp[cur][j]，取更小的。

4. 常见问题与调试心得

这道题在实现时，有几个地方特别容易出错，我结合学生常犯的错误和调试经验来说说。

4.1 数组越界与偏移量设置

这是最经典的错误。dp数组的第二维代表的是“差值下标”，其范围必须涵盖所有可能的最终差值。

• 错误示例1：只计算了初始差值sum_diff的范围[-6000,6000]，于是设置BASE=6000,MAXV=12000。但忽略了旋转操作带来的变化。假设初始差值sum_diff = -6000，然后你旋转了1000张diff=5的牌（change = -10），总变化是-10000，最终差值就是-16000，对应的下标是-16000 + 6000 = -10000，这显然越界了。
• 错误示例2：知道要扩大范围，但算错了。每张牌旋转带来的最大变化是abs(change) = 10，N张牌就是10*N = 10000。所以最终差值范围是[sum_diff - 10000, sum_diff + 10000]。sum_diff本身极值是±6000，所以最终范围是[-16000, 16000]。因此，BASE至少需要16000，MAXV至少需要32000。为了保险和计算方便（比如BASE取整），很多AC代码会直接设BASE = N*5或BASE = 5000，MAXV = 2*BASE+5。我上面的代码取BASE=6000,MAXV=12005对于洛谷的数据是足够的，但更稳健的写法是BASE = 5000，MAXV = 2*BASE + 5。

实操心得：在信奥竞赛中，对于这种带偏移量的DP，我习惯开一个足够大的、固定的数组大小，而不是去精确计算理论边界。例如，直接定义const int M = 10000;和const int BASE = M;，数组大小开2*M+5。用空间换编码安全和思维简洁，在时间限制内是完全可接受的。

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)来比较。

其次，题目要求在最小差值的基础上，找最小旋转次数。所以我们的搜索分两步：

1. 第一优先级：找到最小的abs_diff。
2. 第二优先级：在所有能产生这个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后，我们可以从i=n, j=ans_j开始，根据pre和choice数组倒推回去，就能知道每张牌的选择。

注意事项：记录方案会显著增加空间消耗（从O(N*V)到O(N*V)但多了一个数组）和编码复杂度。除非题目明确要求，否则竞赛中通常不这么做，以节省时间和避免出错。

5.3 时间复杂度的考量

我们的算法时间复杂度是O(N * V)，其中N是牌数（≤1000），V是差值状态数（约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，旋转次数1>0，所以最优是不旋转。
• 输出应为：0

测试用例2：需要权衡

输入： 3 1 2 2 1 3 4

• 牌1: diff=-1, change=2
• 牌2: diff=1, change=-2
• 牌3: diff=-1, change=2
• 初始 sum_diff = -1+1-1 = -1。
• 我们可以尝试：
  • 不旋转：差值=-1，绝对值=1，旋转0次。
  • 旋转牌1：差值=-1+2=1，绝对值=1，旋转1次。
  • 旋转牌2：差值=-1-2=-3，绝对值=3，旋转1次。
  • 旋转牌3：差值=-1+2=1，绝对值=1，旋转1次。
  • 旋转牌1和牌3：差值=-1+2+2=3，绝对值=3，旋转2次。
  • ...
• 最小绝对值是1。能达到绝对值1的方案有：不旋转（0次）、只转牌1（1次）、只转牌3（1次）。取旋转次数最少的，即0次。
• 输出应为：0

测试用例3：边界情况

输入： 1 6 1

• 只有一张牌。diff=5, change=-10。
• 初始 sum_diff=5。
• 不旋转：差值=5，绝对值=5，旋转0次。
• 旋转：差值=5-10=-5，绝对值=5，旋转1次。
• 最小绝对值都是5，取旋转次数少的0次。
• 输出应为：0

调试技巧：

1. 打印DP表：对于小数据（N<=3），可以把整个dp数组打印出来，看看每个状态的值是否如预期。重点关注BASE附近的索引。
2. 手动模拟：像上面测试用例那样，手动计算初始差值、每张牌的change，然后模拟DP过程，与程序输出对比。
3. 检查初始化：确保dp[0][BASE]=0，其他为INF。
4. 检查数组大小：这是最易出错的地方。如果程序在某个测试点发生段错误（Segmentation Fault）或答案错误，首先怀疑MAXV是否够大。可以尝试将其调大（比如翻倍）再测试。
5. 使用在线判题系统的“下载测试数据”功能：如果某个测试点过不了，下载其输入数据，在本地用调试器或打印中间变量来排查。

这道“多米诺骨牌”的题目，很好地融合了01背包和差值处理的思想。它不像裸的背包问题那样直接，需要你先进行一步巧妙的模型转化，把“旋转操作”转化为对“总差值”的调整。一旦转化成功，剩下的就是标准的DP框架了。在信奥赛和算法学习中，这种“转化建模”的能力往往比记忆模板更重要。多练习这类题目，对提升分析问题和设计算法的能力大有裨益。