状态压缩
P1433 吃奶酪 - 洛谷
考虑 DFS, 显然会爆炸. 若到达某一节点时已经吃过了某些奶酪, 我们可以状压一下存储. 当新状态更差时, 停止 DFS.
另一个剪枝: 如果到这个节点已经超过全局最大值, 显然不优. 可能是因为 DFS 常数问题, 产生一个这样的情况不能 continue, 需要 return. 虽然这样剪枝过于激进, 但是能过.
P2622 关灯问题 II - 洛谷
首先可以想到通过搜索查找答案, 由于是找最优解, 考虑 bfs.
由于在一种状态下所产生的新状态是一定的, 故会有重复的搜索状态, 需要判断某种状态是否已经处理到了. $N \le 10$, 灯只有开关两种状态, 可以使用二进制状压存储.
P1896 [SCOI2005] 互不侵犯
由于一个位置能否放国王只与这一行和上一行有关, 因此, 设置dp状态为 dp[i][j][s] 表示第 i 行的状态为二进制串 s, 前 i行放了 j 个国王.
边界条件 dp[0][0][0]=1.
转移条件: 首先从上到下枚举每一行, 再枚举这一行的状态及上一行状态. 如果这两行在一起满足条件, 即可进行转移.
枚举这一行的国王数, 显然, 国王数至少要有这一行的国王数和上一行的国王数, 不能大于 k. 然后对每个国王数进行转移.
注意到, 符合条件的一行的数量是不多的(没有连续的1), 可以先预处理合法的二进制串及其 1 的数量, 在循环时直接处理这些合法的即可.
P1879 [USACO06NOV] Corn Fields
限制: 上下左右不能相邻, 部分田地不能选.
由于一个位置能否选择仅与上一行状态和本行状态有关, 因此, 状态: dp[i][s] 表示第 i 行选取状态为二进制串 s.
边界: dp[0][0]=1.
转移: 枚举行数 当前行状态 上一行状态, 判断能否由上一行转移而来, 若能, 就转移.
其中需要处理贫瘠土地. 用 $M$ 个二进制串表示每一行土地, 若土地是贫瘠的, 就在相应位置标注为 1, 枚举状态时与之按位与即可判断状态是否可行.
与 P1896 [SCOI2005] 互不侵犯 类似, 符合条件的一行的数量是不多的, 故预处理合法的二进制串.
P2704 [NOI2001] 炮兵阵地 - 洛谷
因为当前行的炮兵只会受到前两行的影响, 状态 dp[i][a][b] 表示已经安排了前 i 行, 第 i 行的状态是二进制串 a, 第 j 行是二进制串 b.
还是先预处理一行内合法的情况, 转移过程中枚举本行和前两行的状态, 若其按位与为 0, 意味着没有竖向冲突的阵地, 可以转移. 转移方法: dp[i][x][y] = max(dp[i][x][y], dp[i - 1][y][z] + cnt[w[x]]);
处理山地. 用 $N$ 个二进制串表示每一行土地, 若土地是山地的, 就在相应位置标注为 1, 枚举状态时与之按位与即可判断状态是否可行.
P5911 [POI 2004] PRZ
状态 dp[s] 表示二进制串 s 中为 1 的通过的最短时间. 首先, 预处理每种情况下的重量和通过时间. 初始条件 dp[0]=0, 其余为最大值. 枚举情况 i, 再枚举其子集 j, 表示让子集中的人一次性过桥. 若该子集重量可以通过, 更新答案为 dp[i] = min(dp[i], dp[i ^ j] + t[j]).
P3959 [NOIP 2017 提高组] 宝藏 - 洛谷
状压. dp[i][s] 表示由点集 s 形成的 i 层树的最小代价. 初始状态即为任意一个点, 代价为 0, 即开发商免费打通.
预处理每一个点到一个点集中点的最小距离(直达). 转移过程中, 枚举整个树的点集和最后一层 k 的点集, 显然 k 层点集是整棵树点集的子集. 对两者异或得到出前 k-1 层树的点集, 于是可以计算最后一层中的点到前 k-1 层点的最小距离之和.
至此, 我们发现, 其实对于每一个 k 和相同的点集, 最小距离是相同的. 于是在求出最小距离之和后枚举层数 k, 并更新答案即可.
最终答案: 每一层全节点点集代价的最小值.
Mondriaan’s Dream / 蒙德里安的梦想
这是一道状压好题. dp[i][s] 表示第 i 行状态为二进制串 s, 其中若某一位是 1 则代表相应的一位是向下突出的厕纸. 考虑转移条件:
- 相邻的两行不能同时有一列的向下的厕纸
- 横着摆放的厕纸空间一定要足够. 即算上本行与上一行竖向厕纸后, 剩余的
0一定是多个相邻的偶数长度的块.
第 1 点比较好解决, 按位与之后判断是否为 0 即可. 第 2 点, 我们将相邻两行按位或, 然后转成二进制判断即可.