棋盘上选k个互不同行不同列格子的最大和：二维DP建模精讲

1. 这道题不是考“下棋”，是考你能不能把棋盘变成一张状态表

看到标题里带“Chess”和“二维DP”，很多人第一反应是：哦，国际象棋算法？走马走车？其实完全不是。这道题压根不涉及任何棋类规则的模拟——没有吃子、没有将军、没有王车易位。它只是借用了“棋盘”这个二维网格的物理形态，本质上是一道状态压缩型动态规划的典型建模题。我带过几届算法集训营，每次讲到这道题，总有同学卡在“为什么非得用二维DP”“为什么不能BFS/DFS暴力搜”，后来发现症结不在代码，而在建模意识没转过来：你得先放弃“这是个棋类问题”的直觉，转而问自己——这个网格里，哪些信息必须被记住？哪些状态之间存在确定性转移？

核心关键词“2020年百度之星程序设计大赛（初赛三）1005题”指向一个真实竞赛场景：限时3小时、高强度思维输出、评测系统毫秒级判罚。这意味着解法必须满足三个硬约束：时间复杂度≤O(n²)，空间可压缩，状态定义无歧义。而“Chess”只是出题人埋的一个温和误导——它真正想考察的，是你能否在5分钟内完成从“物理棋盘”到“抽象状态空间”的认知跃迁。适合谁来啃？不是刚学循环的新手，而是已经写过背包、最长上升子序列、编辑距离等经典一维DP，正卡在“多维状态怎么设、怎么转移”这个坎上的进阶学习者。如果你做过“机器人在网格中从左上走到右下，只能向右或向下，求路径最大和”，那恭喜，你已经握住了这道题的半把钥匙；剩下半把，在于理解“状态”如何携带历史决策的全部必要信息。

这道题的原始输入非常干净：一个n×m的棋盘，每个格子有黑白两种颜色，再给定一个整数k。目标是选出恰好k个格子，使得任意两个被选格子既不同行也不同列（注意：不是“不能同行或同列”，而是“既不同行也不同列”——这个逻辑双重否定是审题第一个雷区）。最终要最大化所选格子的颜色值之和（黑为1，白为0，或反之）。表面看是组合选择问题，但暴力枚举C(n×m, k)直接爆炸。二维DP的切入点就在这里：我们不枚举“选哪k个”，而是按行顺序逐行决策，每行最多选1个格子（因为同行格子互斥），同时记录“当前处理到第i行，已选j个格子，且最后一行选的是第c列”——这个三元组(i, j, c)就是状态的核心骨架。但直接存c会带来O(m)空间开销，而题目n,m可达200，k≤200，O(n×k×m)≈8×10⁶勉强可过，但常数大、易写错。真正的优化点在于：我们根本不需要记住“具体哪一列”，只需要知道“之前选过的列集合是否与当前列冲突”。于是状态自然坍缩为dp[i][j]：处理完前i行，恰好选j个格子时，能获得的最大颜色值之和。关键来了——转移时，第i行选第c列，那么前i−1行就不能选第c列。所以dp[i][j] = max{ dp[i−1][j], max_{c=1 to m} (dp[i−1][j−1] + val[i][c]) }？不对。这里漏掉了列冲突约束。正确转移必须确保：如果第i行选了c列，那么前i−1行所有被选的格子，其列号都不能等于c。但dp[i−1][j−1]本身不记录列信息，无法判断是否冲突。这就是为什么必须引入列维度——但不是存具体列号，而是用列状态压缩：用一个m位二进制数mask表示“哪些列已被占用”。然而m=200，2²⁰⁰不可行。所以回到本质：题目只要求“任意两格不同行不同列”，这等价于在棋盘上放置k个“车”（rook），使其互不攻击。而车的放置本质是行与列的一一匹配。因此，最优解必然对应一个大小为k的“行-列匹配子集”。此时问题转化为：在二分图（左部n行，右部m列，边权为格子颜色值）中，求恰好k条边的匹配，使权值和最大。这正是带基数约束的最大权二分匹配，而二维DP正是求解该问题的朴素但稳健的动规框架。我当年在机房调试时，就是靠画出3×3小样例，手动填满dp表，才真正看清状态转移的几何意义：每一行像一道闸门，决定“放不放车”，而列约束则像一条隐形的线，把前面所有决策串成一条链。

2. 状态设计的三重陷阱与破局逻辑

2.1 陷阱一：误把“行列互斥”当“单行单列限制”

最常见错误是这样设状态：dp[i][j] = 前i行选j个格子的最大和。然后转移写成：
dp[i][j] = max( dp[i−1][j], max_{c}(dp[i−1][j−1] + grid[i][c]) )
看起来天衣无缝，实则致命。问题出在dp[i−1][j−1]这个状态里，可能已经包含了第c列的格子。比如第1行选了第3列，第2行又选第3列——这违反了“不同列”约束，但上述转移完全允许。这就是状态信息丢失：dp[i−1][j−1]只告诉你“选了j−1个”，却没告诉你“它们占了哪些列”，导致无法校验冲突。破局关键在于：状态必须携带足够区分冲突的最小信息量。既然列总数m可能达200，存完整mask不可行，那就换思路——我们不关心“具体哪些列被占”，只关心“当前行选某列时，前面有没有人占过它”。这提示我们：状态应按列维度展开，而非行。但题目以行为单位输入，强行按列DP会打乱读入顺序。所以折中方案是：将列索引作为状态第二维，但用滚动数组压缩空间。即定义dp[i][j][c]为“处理完前i行，已选j个格子，且最后一行选的是第c列”时的最大和。但c维度仍为O(m)，总状态O(n×k×m)≈8×10⁶，在C++中可接受（1秒时限），但Java/Python可能超时。更优解是意识到：对于固定i和j，我们只需求max_{c} dp[i][j][c]，而转移时，dp[i][j][c] = max( dp[i−1][j][c], // 第i行不选第c列；dp[i−1][j−1][c'] + grid[i][c] for all c' ≠ c )。这里c' ≠ c的枚举仍是O(m²)。所以必须进一步优化。

2.2 陷阱二：忽视“恰好k个”的强制性与边界处理

很多选手写完主循环，忘了初始化dp[0][0]=0，dp[0][j>0]=−∞（负无穷，表示不可达）。更隐蔽的坑在转移中：当计算dp[i][j][c]时，若j=1，则dp[i−1][j−1][c']对应dp[i−1][0][c']，而dp[i−1][0][c']对所有c'都应为0（选0个格子，和为0），但若初始化为−∞，就会导致dp[i][1][c] = −∞ + grid[i][c] = −∞，全盘崩溃。我见过最惨的一次是某同学本地测小样例全对，一交OJ全WA，查了2小时才发现dp[0][0]写成了−1。另一个边界是i=0（无行）时，只有j=0合法；i>0但j=0时，dp[i][0]应继承dp[i−1][0]，即0。这些看似琐碎的初始化，恰恰是区分“会写DP”和“真懂DP”的分水岭。实际操作中，我习惯用vector<vector<vector >> dp(n+1, vector<vector >(k+1, vector (m+1, LLONG_MIN)))，然后显式dp[0][0][0] = 0？不对，c维度从1开始，所以dp[0][0][c]对所有c都应为0？不，c是“最后一行选的列”，j=0时没有“最后一行”，所以c维度对j=0应无效。因此更合理的状态定义是：dp[i][j]为二维数组，其中dp[i][j][c]仅在j≥1时定义，j=0时单独用dp0[i]表示。但这样增加复杂度。工业级写法是：统一用dp[i][j][c]，对j=0，令dp[i][0][c] = 0（因为没选格子，列无关），但转移时需特殊处理。我最终采用的方案是：定义dp[i][j]为长度为m+1的数组，dp[i][j][c]表示前i行选j个且第j个选在第c列的最大和；同时维护一个辅助数组best[i][j] = max_{c} dp[i][j][c]。这样，dp[i][j][c] = best[i−1][j−1] + grid[i][c]（因为前i−1行选j−1个，无论选在哪列，只要不与c冲突——但等等，best[i−1][j−1]是max值，它对应的列可能正好是c！所以还是冲突）。终于触达本质：冲突约束要求，当我们选第i行第c列时，前i−1行选的j−1个格子，其列集合必须不含c。因此，dp[i][j][c]不能从best[i−1][j−1]转移，而必须从“前i−1行选j−1个且列集合不含c”的最大值转移。这又回到mask问题。但注意到：对于固定i,j，我们需要对每个c快速得到max{ dp[i−1][j−1][c'] | c' ≠ c }。这等价于：已知数组A[c'] = dp[i−1][j−1][c']，对每个c，求A在c'≠c时的最大值。这正是滑动窗口最大值的变种，可用两次预处理解决：left_max[c] = max(A[1..c])，right_max[c] = max(A[c..m])，则max_{c'≠c} A[c'] = max(left_max[c−1], right_max[c+1])。这样，单次转移从O(m²)降到O(m)，总复杂度O(n×k×m)，可接受。

2.3 陷阱三：颜色值处理的符号陷阱与溢出风险

题目中“黑为1，白为0”是简化描述，实际输入可能是字符‘B’/‘W’或整数0/1。但更危险的是：有些版本题面说“黑色格子贡献+1，白色格子贡献−1”，此时最大和可能为负，初始化就不能用0，而必须用LLONG_MIN。我遇到过一次线上事故：某高校校赛复刻此题，数据生成器脚本有bug，导致部分测试点白色格子数远超黑色，最优解为负，而选手全用int初始化dp为0，结果WA on test 7。此外，n,m,k上限均为200，grid[i][c]为±1，最大和绝对值≤200，int足够，但中间状态如best[i][j]可能参与多次加法，为防意外，一律用long long。还有一个隐藏坑：输入格式。百度之星常用空格分隔，但棋盘数据可能有多余空行或末尾空格。我习惯用while(cin >> s && !s.empty())读入，但更稳妥的是getline后trim。实操心得：在竞赛中，宁可多写3行健壮输入，也不要省这一步赌RP。

3. 完整实现与核心环节逐行解析

3.1 数据结构与初始化：滚动数组的取舍权衡

我们采用空间优化版：因dp[i]只依赖dp[i−1]，故用两个二维数组滚动：prev[j][c]和curr[j][c]，其中j∈[0,k]，c∈[1,m]。但j=0时c无意义，所以将j=0单独处理。最终结构如下：

// C++ 实现（可直接AC） #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = -1e18; // 负无穷，表示不可达 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; // 读入棋盘，grid[i][j] 表示第i行第j列（1-indexed）的值：黑=1，白=0 vector<vector<int>> grid(n+1, vector<int>(m+1, 0)); for (int i = 1; i <= n; i++) { string s; cin >> s; for (int j = 1; j <= m; j++) { grid[i][j] = (s[j-1] == 'B') ? 1 : 0; // 注意s索引从0开始 } } // dp[j][c] 表示：当前处理到某行，已选j个格子，且最后一个选在第c列时的最大和 // 初始化：全为-INF，表示不可达 vector<vector<ll>> dp(k+1, vector<ll>(m+1, INF)); // base case: 选0个格子，和为0，但此时无"最后一列"，所以j=0状态单独处理 // 我们约定：dp[0][c] 不使用，j=0时用单独变量 best0 表示 ll best0 = 0; // 前i行选0个的最大和，恒为0 // 按行DP for (int i = 1; i <= n; i++) { // 新的状态数组，初始化为-INF vector<vector<ll>> new_dp(k+1, vector<ll>(m+1, INF)); // j=0：不选任何格子，和为0 for (int c = 1; c <= m; c++) { new_dp[0][c] = 0; // 实际上c无关，但为统一结构设为0 } // 对每个j从1到k for (int j = 1; j <= k; j++) { // 预处理：对上一行的dp[j-1][*]，计算每个c对应的 max{ dp[j-1][c'] | c' != c } // 即：排除c列后的最大值 vector<ll> prev_row(m+1); // prev_row[c] = dp[j-1][c] from previous row for (int c = 1; c <= m; c++) { prev_row[c] = dp[j-1][c]; } // 计算 left_max[c] = max(prev_row[1..c]) vector<ll> left_max(m+2, INF); for (int c = 1; c <= m; c++) { left_max[c] = max(left_max[c-1], prev_row[c]); } // 计算 right_max[c] = max(prev_row[c..m]) vector<ll> right_max(m+2, INF); for (int c = m; c >= 1; c--) { right_max[c] = max(right_max[c+1], prev_row[c]); } // 现在对当前行第i行，每个列c，计算 new_dp[j][c] for (int c = 1; c <= m; c++) { // 方案1：不选第i行第c列 -> 继承上一行的new_dp[j][c]？不，new_dp是新的 // 实际上，new_dp[j][c] 只考虑以c结尾，所以必须选c // 因此只有一种转移：选第i行第c列，则前i-1行需选j-1个且不占c列 ll best_prev = INF; if (j == 1) { // 选第一个格子，前面没选，所以best_prev = 0（选0个的和） best_prev = best0; } else { // j>=2：需要 max{ prev_row[c'] | c' != c } if (c > 1) best_prev = max(best_prev, left_max[c-1]); if (c < m) best_prev = max(best_prev, right_max[c+1]); } if (best_prev != INF) { new_dp[j][c] = best_prev + grid[i][c]; } } } // 更新dp为new_dp，并更新best0 dp = move(new_dp); // 同时，best0保持为0，因为选0个永远是0 } // 最终答案：max{ dp[k][c] for all c }，即选k个且最后一列是c的最大值 ll ans = INF; for (int c = 1; c <= m; c++) { ans = max(ans, dp[k][c]); } // 但还有一种可能：k=0，此时ans应为0 if (k == 0) ans = 0; cout << ans << '\n'; }

这段代码的关键在于3.1节的预处理逻辑。left_max和right_max数组的构建是O(m)的，避免了对每个c都遍历所有c'的O(m²)暴力。best_prev的计算体现了“排除当前列c后，前i−1行选j−1个的最大值”这一核心思想。注意j==1的特判：此时前i−1行选0个，和为0，无需查prev_row。move(new_dp)是C++11的移动语义，避免深拷贝，提升效率。整个算法时间复杂度O(n×k×m)，空间O(k×m)，在n,m,k≤200时，n×k×m=8×10⁶，现代CPU可在100ms内完成。

3.2 核心转移的几何可视化：把DP表当成棋盘投影

为了彻底理解转移，我建议手动画一个2×3小棋盘：
行1：B W B → [1,0,1]
行2：W B W → [0,1,0]
k=2

初始化：dp[0][*]全INF，best0=0

处理i=1（第1行）：

• j=1：prev_rowfor j-1=0 is not used, so best_prev = best0 = 0
  • new_dp[1][1] = 0 + 1 = 1
  • new_dp[1][2] = 0 + 0 = 0
  • new_dp[1][3] = 0 + 1 = 1
• j=2：跳过（i=1行不够选2个）

处理i=2（第2行）：

• j=1：同上，new_dp[1][1]=0+0=0, [1][2]=0+1=1, [1][3]=0+0=0
• j=2：需用i=1行的dp[1][*] = [1,0,1]
  • 对c=1：排除c'=1，max(c'=2,3) = max(0,1) = 1 → new_dp[2][1] = 1 + 0 = 1
  • 对c=2：排除c'=2，max(c'=1,3) = max(1,1) = 1 → new_dp[2][2] = 1 + 1 = 2
  • 对c=3：排除c'=3，max(c'=1,2) = max(1,0) = 1 → new_dp[2][3] = 1 + 0 = 1
    最终max(new_dp[2][*]) = 2，对应选(1,1)和(2,2)或(1,3)和(2,2)，和为1+1=2，正确。这个手工推演过程比看10行代码更管用。我带学生时，强制要求每人画一遍3×3，画错三次以上才给看代码。

3.3 输入输出的鲁棒性加固：竞赛环境下的生存指南

竞赛OJ环境千奇百怪：有的用Windows换行符\r\n，有的输入末尾有空格，有的甚至有多余空行。上面代码的cin >> s在遇到空行时会失败。生产级加固如下：

// 替换原读入部分 vector<string> lines; string line; while (getline(cin, line)) { // trim leading and trailing spaces line.erase(0, line.find_first_not_of(" \t\r\n")); line.erase(line.find_last_not_of(" \t\r\n") + 1); if (!line.empty()) lines.push_back(line); } if (lines.size() < n+1) { // 输入不足，报错或补默认值 cerr << "Input error: expected " << n+1 << " lines, got " << lines.size() << endl; return 1; } // 解析n,m,k from lines[0] stringstream ss(lines[0]); ss >> n >> m >> k; // 解析棋盘 from lines[1] to lines[n] for (int i = 1; i <= n; i++) { string s = lines[i]; if (s.length() < m) s += string(m - s.length(), 'W'); // 补白 for (int j = 1; j <= m; j++) { grid[i][j] = (s[j-1] == 'B') ? 1 : 0; } }

这个加固版本能应对99%的OJ输入异常。另外，INF的取值很重要。-1e18足够小，但若用INT_MIN，在加法中可能溢出为正数，导致逻辑错乱。long long的LLONG_MIN是−2⁶³，但某些编译器对LLONG_MIN的字面量支持不好，所以用-1e18更稳妥。最后，输出必须用'\n'而非endl，后者会flush缓冲区，拖慢IO。

4. 常见问题与排查技巧实录

4.1 WA（Wrong Answer）高频原因速查表

我踩过最深的坑是第2条：某次比赛，输入文件末尾有不可见Unicode字符，getline读入后s.length()比预期大1，导致grid[i][j]访问s[j-1]越界，读到垃圾值。解决方案是：s = s.substr(0, m);强制截断。

4.2 TLE（Time Limit Exceeded）性能瓶颈定位

当n=m=k=200时，理论操作数约8×10⁶，C++应<100ms。若TLE，必有隐藏循环：

• 检查是否写了O(m²)转移：如对每个c，内层再遍历所有c'。用left_max/right_max预处理是唯一出路。
• 检查IO是否成为瓶颈：cin未关同步，或cout用endl。加入ios::sync_with_stdio(false); cin.tie(nullptr);是标配。
• 检查vector是否频繁resize：new_dp在每行都新建，但vector<vector<ll>>的构造是O(k×m)，总O(n×k×m)=8×10⁶，可接受。但若写成new_dp[j].push_back(...)动态添加，则退化为O(n×k×m²)。

性能分析工具：在Linux下用time ./a.out < in.txt，看real time。若>500ms，用gprof或perf分析热点。但竞赛中，直接看代码循环嵌套层数更高效。

4.3 从AC到满分：边界测试用例清单

光过样例不够，必须覆盖以下边界：

1. k=0：答案必须为0。测试：n=1,m=1,k=0，输入任意棋盘。
2. k=1：答案应为棋盘最大值。测试：n=1,m=3,k=1，输入"BWW"，期望1。
3. k > min(n,m)：不可能选k个互不同行列的格子，答案应为-INF（但题目保证有解，所以通常k≤min(n,m)）。测试：n=2,m=2,k=3，应输出-INF或题目说明无解。
4. 全白棋盘：所有grid[i][j]=0，答案恒为0。
5. 单行多列：n=1,m=200,k=1，检验是否O(m)而非O(m²)。
6. 单列多行：n=200,m=1,k=1，此时只能选1个，答案为该列最大值。

我维护了一个test.sh脚本，自动生成这6类测试，一键运行：

# 生成k=0测试 echo "1 1 0" > in0.txt echo "B" >> in0.txt ./a.out < in0.txt # 应输出0

每天刷题前，先跑一遍边界测试，能省下80%的debug时间。

4.4 进阶思考：这道题还能怎么变？

掌握本题后，可自然延伸至三类变体，检验是否真懂：

• 变体1：最小化和：只需把max换成min，INF换成LLONG_MAX，逻辑完全对称。
• 变体2：带权重的列代价：选第c列需额外付出cost[c]，则转移变为new_dp[j][c] = best_prev + grid[i][c] - cost[c]。
• 变体3：三维DP扩展：若约束升级为“任意两格不同行、不同列、且曼哈顿距离>2”，则状态需增加坐标信息，复杂度升至O(n×m×k×m)，需进一步优化。

最后分享一个小技巧：在考场手写DP时，先在草稿纸上画出状态转移的“箭头图”——从dp[i-1][j-1][c']指向dp[i][j][c]，并标注条件c' ≠ c。这个图比任何文字描述都直观。我见过太多同学盯着屏幕敲代码，不如花2分钟画图，一画就通。