#创人计划# OI 界将迎来大变

userId_undefined
cjdst
尊贵铂金CSP-S一等奖代码纠察员出题人

2025-10-08 22:17:19

发布于：广东

88阅读
0回复
0点赞

众所周知，朴素的状压 DP 是 O(2n)O(2^n) 起步的，非常慢。

我们可以按照折半搜索（Meet-in-the-Middle）的思想，只枚举所有 11 的位不超过 ⌈n2⌉\lceil\frac{n}{2}\rceil 的数，然后两两结合就行了。

例如最短 Hamilton 距离我们多开一维表示起始位置，按上面的方法处理出这些 DP，最后不是要求状态为 2n−12^n-1 的最小值吗，我们只需要枚举所有 11 的位不超过 ⌈n2⌉\lceil\frac{n}{2}\rceil 的 kk，找到 dp[1][k][i]dp[1][k][i] 与 dp[i][2n−k−1][j]dp[i][2^n-k-1][j] 的和的最小值就行了。

注意到这样子总状态数量为 (n1)+(n2)+(n3)+...+(n⌈n2⌉){n\choose 1}+{n\choose 2}+{n\choose 3}+...+{n\choose \lceil\frac{n}{2}\rceil}，

显然远远小于朴素状压的 (n1)+(n2)+(n3)+...+(nn−1)+(nn){n\choose 1}+{n\choose 2}+{n\choose 3}+...+{n\choose n-1}+{n\choose n} 状态数量。

userId_undefined
去预览
0/2000

全部评论 14

热门讨论