状压DP：二进制优化与竞赛应用

markdown复制## 1. 状压DP的本质与竞赛价值

第一次接触状压DP是在准备CSP-S复赛时遇到的一道棋盘覆盖问题。当时盯着题目看了两小时毫无思路，直到学长提醒"试试把每一行的摆放状态用二进制表示"，才恍然大悟。状压DP（状态压缩动态规划）本质上是通过二进制数来高效表示和转移复杂状态的一种技巧，在信奥赛提高组中属于必须掌握的进阶算法。

为什么CSP-S/NOIP中状压DP如此重要？从近年真题来看，约30%的动态规划题目都涉及状态压缩。比如2021年CSP-S第二轮"网格染色"问题，纯暴力解法时间复杂度是O(n!)，而采用状压DP能优化到O(n*2^n)。这种指数级优化往往就是能否拿到100分的关键。

## 2. 状态压缩的核心思想

### 2.1 二进制表示的艺术

状压DP最精妙之处在于用二进制位的0/1表示布尔状态。例如在经典旅行商问题(TSP)中：
- 城市访问状态"1011"表示：已访问城市1、3、4（从右往左数）
- 这个状态对应的十进制数是11
- 状态总数从n!降为2^n

实际编程中常用位运算加速：
```cpp
// 检查是否访问过城市i
if (state & (1 << i)) {...}

// 标记城市i为已访问
new_state = state | (1 << i);

2.2 状态设计的三个原则

1. 无后效性：当前状态应包含所有影响后续决策的信息
2. 可转移性：能从已知状态推导出后续状态
3. 紧凑性：用尽可能少的位数表示状态（通常int够用，超限时用bitset）

3. 经典问题实战解析

3.1 棋盘覆盖问题

题目：在n×m的棋盘上放置1×2骨牌，求无重叠覆盖的方案数（n,m≤8）

状态设计：

• dp[i][state]：处理到第i行时，该行覆盖状态为state的方案数
• state的二进制位表示该格是否被覆盖（注意横放会占用两格）

关键转移代码：

cpp复制for (int i = 1; i <= n; ++i) {
    for (int prev = 0; prev < (1<<m); ++prev) {
        if (!dp[i-1][prev]) continue;
        dfs(i, 0, prev, 0