★ FEATURED ARTICLE 刷题刷到一道COCI老题题目叫P4329 Bond。题面请出007当背景有n个特工、n个任务第i个特工完成第j个任务的概率用百分比给出要求你安排一个一对一的分配方案使所有特工同时行动时全部任务成功完成的概率最大。我第一反应是这不就是二分图最大权匹配吗但细看才发现问题不简单——题目要最大化的是多个概率的乘积不是权值之和。多亏n≤20这个条件足够友好状态压缩DP可以直接一路推过去。这篇文章就把我解这道题的完整思路、C实现、调试时踩过的坑以及旁边的一些替代解法都整理出来给同样在练状压DP和排列优化的信奥选手做个参考。1. 先别急着写代码为什么贪心和KM都救不了这道题1.1 题目原貌一次真实的007任务分配先看清楚题面到底在问什么。假设有n个特工编号0到n-1同时有n个任务编号0到n-1。给你一张n×n的表格第i行第j列表示特工i单独执行任务j的成功概率范围是0到100的整数。你要做的是把每个任务恰好分配一个特工每个特工恰好领一个任务。因为所有特工是同时行动的任何一个特工失败都意味着本次行动整体失败所以整体成功率等于每个特工成功概率的乘积。举个例子n2时表格是特工\任务任务1任务2特工A10050特工B50100如果让特工A做任务1、特工B做任务2整体成功率是100%×100%100%。如果交叉分配则是50%×50%25%。很明显要让成功率高的组合尽量互相匹配。n最大到20也就是说最多有20个特工和20个任务需要从20!种排列中找出一个最大乘积的排列暴力必然不可能。这道题真正考验人的地方不是题面包装得多花哨而是你能不能从排列最大化乘积这个描述里第一时间想到状态压缩DP。COCI把它放在第一轮算是中等偏上难度的经典题洛谷上它的标签几乎都指向状压DP但如果你只背过模板不看穿乘积这个关键点照样会写歪。1.2 贪心反例两次局部最优如何翻车拿到最大化乘积很多人第一反应是贪心先找一个成功率最高的(i, j)组合把这个任务分配出去然后递归处理剩下的人。这个思路听起来很顺实际上翻车概率极高。我给你一个反例特工\任务任务1任务2特工A10090特工B901全局成功率最高的单个组合是A做任务1的100%。贪心会先把任务1给A剩下B只能做任务2整体成功率100%×1%1%。但最优方案明显是A做任务290%、B做任务190%整体成功率90%×90%81%。两种方案差了整整80个百分点这才n2就翻车了。这个反例的本质是贪心只看到某个特工对某个任务的个人成功率很高却忽略了它占住这个任务后会让其他特工陷入极低概率的境地。因为整体是乘法任何一个环节是低概率都会把整个乘积拉下来。所以分配时必须在每个人选什么任务之间做全局权衡这种牵一发动全身的问题正好是动态规划擅长的。也有人会想那是不是可以按概率从大到小的顺序排序后一个一个处理同样不行。概率大小只是优化方向不代表最终决策。你按高概率排序先处理的人可能抢走另一个组合中需要的任务导致后面的乘积崩塌。这类问题不满足贪心选择性质没有一条捷径可以绕开枚举状态。1.3 乘积模型与求和模型的本质区别如果再往深想一层会发现这道题和经典的最大权二分图匹配有着微妙差别。最大权匹配要最大化的是Σw(i, j)这时候可以用KM算法或者最小费用最大流。但Bond要最大化的是Πp(i, j)这是乘法结构不是加法结构。乘法结构有一个常见的数学技巧取对数。把每个概率变成ln(p(i, j))之后最大化乘积就等价于最大化Σln(p(i, j))因为ln是单调递增函数。理论上这条路也能走通配合KM算法求最大权匹配就能解。但这么做的麻烦在于第一取对数之后全是浮点数精度处理要小心第二KM算法本身实现起来比状压DP复杂第三n≤20的时候状压DP的时间和代码量都更友好没必要引入一个更复杂的算法。这里还想强调一个关键点为什么不能直接用加法DP的思维去套因为加法DP里每个转移是加一个数值而Bond这里是乘一个概率。乘法意味着dp状态里存放的值是累积概率乘积而概率都在0到1之间乘完之后值只会越来越小。这点在调试时特别容易困惑——你发现dp的值越推越小不要以为自己写错了这是乘法累积的正常现象。只要保证每一步取的是最大乘积最终答案就是全局最优。2. 状压DP建模把任务分配状态压缩成一个二进制数2.1 n≤20就是状态压缩的入场券为什么看到n≤20就能条件反射想到状态压缩因为2^201,048,576这个数字对计算机来说非常友好。开一个长度100万出头的double数组也就8MB左右遍历一遍也就一千万量级的操作稳稳跑进一秒。反过来如果n302^30已经是10亿级别状态压缩就直接爆炸了那就要另想办法。在Bond这道题里真正需要记住的状态是哪些任务已经被分配出去了以及当前分配到了第几个特工。任务总数有n个每个任务只有被占用和未被占用两种情况这正好对应二进制位。用一个整数mask表示任务占用集合mask的第j位是1就表示任务j已经被分配是0就表示还没人接走。这个mask就是状态压缩的载体。有人可能会问为什么不把分配到了第几个人也存进状态答案是可以不存。因为我们固定按照特工编号从小到大安排最后一个进入状态的人是谁根本不重要只需要知道已经安排了几个。而安排了几个恰好等于mask中1的个数也就是二进制中popcount(mask)。这样就省掉一维只用一维数组dp[mask]就能表示全部状态。这个用popcount人数代替显式人数的技巧在状压DP里非常常见。它的意义是让状态定义更紧凑转移更自然。很多排列类问题都可以这样抽象当前已经处理了前k个对象并且占用集合为maskk和mask中1的个数自动保持一致不需要额外记录。2.2 状态定义、转移方程与按mask递增的巧妙之处现在给出标准状态定义。设dp[mask]表示已经安排了前popcount(mask)个特工他们分别占用了mask中对应位置的任务在这种前提下所有已分配特工成功概率乘积的最大值。初始化是dp[0]1.0因为一个任务都没分配、一个特工都没出场时成功概率乘积可以看作1。转移方程非常直接。假设当前状态是mask已经安排的人数ipopcount(mask)那么下一个要安排的就是特工i。他在所有未被占用的任务j中选一个转移后状态变成mask|(1j)也就是把任务j的二进制位置为1。新的概率是dp[mask]乘上特工i对任务j的成功概率p[i][j]。因为可能有多个前驱状态转移到同一个后继状态我们要对每个后继状态取最大值。写成公式就是dp[mask|(1j)] max(dp[mask|(1j)], dp[mask] × p[i][j] / 100.0)这个转移之所以能只用一维数组是因为mask|(1j)这个值在数值上一定大于mask。为什么因为j位原本是0置为1后整个整数增加了2^j所以一定会变大。这就意味着只要按mask从0到full-1递增的顺序遍历任何状态的转移目标都排在它后面不会被重复利用。换句话说一维dp数组在遍历到每个mask时它的所有可能前驱都已经计算过了可以直接安全读取。这个结论非常关键。很多人在写外层套人的版本时还要担心同一轮内一个特工被用两次的问题而按mask递增的写法天然规避了这个问题。状态转移和顺序的关系我会在实现部分用代码进一步说明。2.3 手工推一遍3×3样例看DP值怎么长出来光看公式不够直观我拿一个3×3的例子手推一遍。假设输入是3 40 30 20 20 30 90 10 80 30先全部转换成0到1的小数p[0]{0.4,0.3,0.2}p[1]{0.2,0.3,0.9}p[2]{0.1,0.8,0.3}。初始化dp[000]1.0。第0个特工上场dp[001]1.0×0.40.4特工0做任务1dp[010]1.0×0.30.3特工0做任务2dp[100]1.0×0.20.2特工0做任务3第1个特工上场状态mask里1的个数必须等于1从dp[001]出发任务2、任务3没被占用。做任务2dp[011]0.4×0.30.12做任务3dp[101]0.4×0.90.36。从dp[010]出发任务1、任务3没被占用。做任务1dp[011]更新为max(0.12, 0.3×0.20.06)0.12做任务3dp[110]0.3×0.90.27。从dp[100]出发任务1、任务2没被占用。做任务1dp[101]更新为max(0.36, 0.2×0.30.06)0.36做任务2dp[110]更新为max(0.27, 0.2×0.80.16)0.27。第2个特工上场此时需要状态里1的个数等于2从dp[011]出发只剩任务1。dp[111]max(0, 0.12×0.10.012)。从dp[101]出发只剩任务2。dp[111]max(0.012, 0.36×0.80.288)。从dp[110]出发只剩任务3。dp[111]max(0.288, 0.27×0.30.081)0.288。最终dp[111]0.288乘以100输出就是28.800000。对应方案是特工0做任务10.4、特工1做任务30.9、特工2做任务20.8三者相乘正好0.4×0.9×0.80.288。可以肉眼验证这个方案确实比其它组合更高说明DP真的把最优方案找出来了。3. C实现一维dp数组的写法与所有精度细节3.1 可直接AC的完整代码直接上代码这段是我实际调试完觉得最稳的写法关键点都用注释标了#include bits/stdc.h using namespace std; int n; double p[25][25]; double dp[1 20]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 0; i n; i) { for (int j 0; j n; j) { int x; cin x; p[i][j] x / 100.0; } } int full 1 n; // 预处理每个mask里1的个数popcount vectorint popcnt(full, 0); for (int mask 1; mask full; mask) { popcnt[mask] popcnt[mask 1] (mask 1); } dp[0] 1.0; for (int mask 0; mask full; mask) { int i popcnt[mask]; // 已经安排了多少个特工 if (i n) continue; // 全部安排完了 if (dp[mask] 0.0) continue; // 该状态概率是0没必要继续 for (int j 0; j n; j) { if (mask (1 j)) continue; // 任务j已被占用 int nxt mask | (1 j); double val dp[mask] * p[i][j]; if (val dp[nxt]) { dp[nxt] val; } } } cout fixed setprecision(6) dp[full - 1] * 100.0 \n; return 0; }这段代码有几个设计选择值得说明。首先是读入时直接把整数概率除以100转换成0到1的小数。为什么不最后再除因为dp在转移时要连乘如果全程用整数百分比乘中间值会越乘越大最后统一除反而不直观还容易在乘法过程中产生非常大的中间结果。虽然double能扛住20次乘100的累积但没必要冒这个风险。从输入就直接变成小数更符合概率乘法的自然顺序。第二是预处理popcnt数组。这样在遍历每个mask时可以O(1)拿到当前已经安排的人数不需要反复调用内建函数。虽然__builtin_popcount本身很快但在一千万次循环里少一次函数调用总是好的而且这段预处理代码本身只有两行几乎不增加负担。第三是if (dp[mask] 0.0) continue这个剪枝。在随机数据里因为概率经常出现0很多mask的dp值会一直保持0跳过它们能省下一大块乘法运算。实际测试中这个剪枝对随机数据能带来大约20%到50%的性能提升对n20的满数据来说尤其明显。3.2 位运算优先级和转移顺序两个经典翻车点第一个翻车点是位运算优先级。我见过不少人写if (mask (1 j) 0)这在C里是致命的。原因是在C的运算符优先级中的优先级高于所以这个表达式会被解析成mask ((1 j) 0)产生一个完全不符合预期的值。正确写法是if (!(mask (1 j)))或者if ((mask (1 j)) 0)。这个问题在代码里隐蔽性极强因为它不会直接编译报错只会让判断逻辑混乱导致答案错得莫名其妙。我在本地调试时一度看到dp[full-1]算出来是0排查了很久才发现是这里括号漏了。第二个翻车点是转移顺序。最开始我脑子里的循环是先枚举特工再枚举mask写出来的代码如下for (int i 0; i n; i) { for (int mask 0; mask full; mask) { if (popcnt[mask] ! i) continue; for (int j 0; j n; j) { if (mask (1 j)) continue; int nxt mask | (1 j); dp[nxt] max(dp[nxt], dp[mask] * p[i][j]); } } }这里最隐蔽的坑是外层i循环中当i固定时mask从小到大遍历。当前状态mask的popcnt是i但转移目标nxt的popcnt是i1它在本轮i中也会被遍历到。虽然if (popcnt[mask] ! i) continue会把这些nxt状态跳过不会让特工i被用两次但dp[nxt]在本轮被更新后并不会马上被同一轮的其它状态使用而是在下一轮i1中才会作为源状态。从逻辑上这其实没错运行时也没问题。真正出问题的是另一种写法有人为了让转移目标能被顺序访问把内层mask倒着遍历但从full-1往下走这样nxt数值更大已经被访问过了也不会被重复使用。两种方向都可能让人绕晕。相比之下我推荐最开始那种一维dp按mask递增的写法它的逻辑链条最短转移目标数值永远大于源状态递增遍历保证了每个状态在被访问时已经是最终值不需要额外考虑轮次。这是我在调了两次顺序错误之后沉淀下来的最不容易出错的实现方式。3.3 百分比输入、double乘法与输出格式的坑输出格式这一关卡的比较隐蔽。题目要求输出的是百分比形式的概率保留6位小数。也就是说如果整体成功率是0.288你要输出的是28.800000而不是0.288000。所以代码最后要乘100。我一开始没乘100直接输出fixed setprecision(6)结果是0.288000看着也像六位小数但和样例对不上判题直接WA。后来才意识到题目要的是百分比不是概率小数。这个其实看样例就能发现但很多人读完一遍题根本没注意包括我自己。另一个和浮点相关的细节是double在连续乘20次概率后是否够精确答案是绝对够。20个double连乘每个概率都在0到1之间浮点误差累积量级远小于1e-12而输出只保留6位小数完全不影响。所以这道题没有必要上long double用double就行。如果硬要用long double输出时还要注意类型转换反而多出麻烦。还有一个值得说的小点cout fixed setprecision(6)对精度是固定小数点后六位这符合题目要求。如果用setprecision(6)不带fixed它输出的是有效数字位数如果答案是100会输出100而不是100.000000这是必WA的。所以fixed这个修饰符一定不能漏。4. 性能实测与替代思路从理论复杂度到真实评测4.1 O(n·2^n)到底怎么算出来的很多博客说这题复杂度是O(n·2^n)但没解释清楚这个n怎么来的。简单说一下状态总数是2^n每个状态在转移时要枚举所有n个任务判断是否已经被占用。所以最内层操作的次数上限约等于n×2^n。把n20代进去就是20×1,048,576大约2100万次浮点乘法和比较。这个量级在C里跑得非常快实测本机大概0.1到0.3秒放到评测机上也没什么压力。内存占用也完全可以接受。dp数组是double类型长度为2^20占8MB左右popcnt是int数组再占4MB左右。总内存也就12MB上下远低于常见的256MB限制。还有一个容易被忽略的效率点dp[mask] 0.0的剪枝。在最坏情况下如果所有概率都正好是0到100的随机整数大约有(101/101)种组合都可能不为0实际上只要概率非零从初始状态能到的状态就不少。但即便如此很多mask因为被多个来源竞争只有一个来源能留到最后中间还是会产生大量被覆盖的无效状态。跳过dp[mask]0的状态可以让实际执行时间进一步下降。这个剪枝在官方数据上效果稳定不会改变结果正确性非常安全。4.2 记忆化DFS剪枝为什么能写但不如DP稳除了DP这道题也能用记忆化DFS加剪枝做。思路是从第0个特工开始递归记录当前安排到了第几个人以及任务占用状态同时维护当前概率乘积到n个人全部安排完就更新答案。因为每个特工选择任务的分支是n!级别n20时直接搜完全不可行所以必须剪枝。一个常用的剪枝方法是预处理一个上界估计。对每个尚未处理的特工找出他在所有任务中的最大概率mx[i]然后计算一个后缀上界suf[i] mx[i]×mx[i1]×...×mx[n-1]。在搜索过程中如果当前累积概率cur乘上suf[i]仍然小于已经找到的答案ans那这条分支无论如何都不可能超越当前最优解可以直接剪掉。这个剪枝在很多数据上确实有效甚至比DP更快因为搜索往往能迅速找到一个不错的可行解然后用上界剪掉大量分支。但它的缺点是上界估计是宽松的也就是说很多分支虽然满足剪枝条件但实际仍可能包含最优解不如果cur×suf[i]≤ans那确实不可能超过ans因为每个特工的真实概率都≤各自最大值所以剪枝是安全的。然而在构造的数据里如果所有概率都很高且接近上界剪枝失效搜索仍会退化到接近全排列搜索。因此竞赛中我更推荐状态压缩DP它不依赖数据强度最坏情况也有确定的时间复杂度。如果你对DFS剪枝特别感兴趣把它作为思考题去加深对分支上界的理解是很好的。但直接提交的话DP的稳定性远高于搜索。这是我在对比两种写法之后的实际感受。4.3 0概率分支的剪枝优化实测还有一种针对特定数据形态的优化值得单独说输入中经常出现概率为0的情况这意味着某些特工完全不适合某类任务。如果dp[mask]为0它转移出去的分支乘出来必定也是0对最终答案没有任何帮助可以直接跳过。这个优化我已经在代码中实现了实测量级并不大但对随机数据的效果很明显。有同学问能不能在转移时再加一个如果p[i][j]0就不更新dp[nxt]的判断也可以。因为p[i][j]为0时val必然为0除非dp[nxt]本身也是0否则不会覆盖任何有效结果。加上这个判断能减少一次无意义的乘法但收益其实很小因为乘法本身很快。真正有价值的是前面的dp[mask]0剪枝它把整棵转移子树都砍掉了而不只是砍掉当前一条边。这里我还想提一个关于数据类型的实际经验概率p[i][j]读入时是整数如果你把它存在double数组里每次转移都要做浮点乘法。如果你用int存读入值转移时再除以100就需要在循环里做一次除法反而更慢。最划算的做法是我代码里的方式读入时一次性把int变成double后续全程浮点乘法。5. 从Bond延伸开这类乘积型排列问题的通用解法与其启发5.1 状态压缩DP的套路化迁移把Bond吃透之后你会发现自己对一类题都有了手感。这类题的共同特征是n不超过20需要将若干对象分配到若干位置每个对象的收益依赖具体分配位置目标函数是总的收益最大化或最小化而且通常是排列问题不能用简单的贪心解决。套路非常固定定义dp[mask]表示当前占用集合为mask时的最佳值转移时枚举最后一个加入集合的元素或者下一个加入的元素。Bond是枚举下一个加入的任务同时固定了加入顺序是特工编号依次递增。TSP旅行商问题是枚举最后一个到达的城市然后从它再走一步到新城市。排列最大化这类题本质上都是增量构造一个排列的DP。还有一个变种需要注意有时状态不止一个维度比如有A、B两组对象要配对每组各n个这时候一个mask不够可能需要dp[aMask][bMask]双状态压缩。但万变不离其宗核心依然是用一个整数集合记住消耗过的东西用一个popcount记住已经用到第几个单位。Bond虽然是一维但它把人数用popcount推导的技巧展现得淋漓尽致。如果你在刷题时看到n≤20、排列、全部成功/全部完成这些关键词第一反应就应该想到状压DP第二反应是考虑目标函数是加法还是乘法。加法用max累加乘法用max多次乘。取对数可以把乘法变加法必要时还能换用KM或费用流但小数据量下状态压缩永远是第一优先级的思路。5.2 我个人调试这道题的几点体会最后聊一点调试心得。我第一次交这题的时候WA得很惨输出结果比正确值还大甚至出现超过100%的荒谬结果。当时第一反应是精度出了问题排查了半天发现根本不是double的锅。真正的bug出在我把任务概率处理成了整型百分比在dp里直接连乘阶段性地除以100结果某条路径被重复除了一次概率反而被放大了。后来改成读入时统一除以100问题立刻消失。第二个体会是这类乘积DP的中间值会越来越小而加法DP的中间值通常越来越大这会导致调试心态不同。如果你看到dp数组里很多状态是0或者极小值不要慌这是正常的。真正需要关注的是dp[full-1]最终值能不能和手推的答案一致。建议遇到n3的小样例像我在第3节里那样把每一步转移都打印出来比对着代码猜要快得多。第三个体会也是最实际的考试和刷题的时候代码越简单越好。Bond这题明明可以用更复杂的KM算法、费用流、对数转换去解但n≤20的现实条件下一维dp数组加位运算就是最优解。写题不是炫技是用最可靠的工具解决问题。我从这道题里最大的收获不是记住了Bond的解法而是记住了一个重要的做题原则看到数据规模先把最简单的可行方案想清楚再考虑优化空间。
阅读完成 · 觉得有帮助？
