状态压缩动态规划（二）

[[ slider_text ]]

[[ item.c ]]

状态压缩动态规划（二）

发布时间 2024-09-11 作者：zhangminchen 来源：算法小站

状态压缩dp 期望dp

## CCPC 女生专场 2021 C
**[CCPC 女生专场 2021 C 连锁商店](https://codeforces.com/gym/103389/problem/C)**
**问题描述**
给定$$n$$个点的有向无环图，每个点有颜色$$c_i$$，权值是$$w_i$$
从$$1$$号点走到$$i$$号点，在路径中选择一些颜色两两不同的点，使得权值和最大
对于每一个$$i$$输出答案

### 算法分析
类似**TSP问题**，$$dp(S, i)$$表示当前选的**颜色**的状态是$$S$$，当前在$$i$$号点，能得到的最大权值
那么枚举$$j$$，如果$$c_j \neq c_i$$，有转移$$dp(S \mid c_j, j) \leftarrow dp(S, i) + w(c_j)$$

实际上还有冗余状态，注意到，如果对于一种颜色$$x$$，它只有一个点，那么它一定会被选进来
这时候不需要记到$$S$$中去，$$S$$只记录那些有$$\geqslant 2$$个点的颜色
dp 做完之后，再单独把那些只出现一次的颜色加上去，即可

### 算法实现
对于**有向无环图**，$$dp$$的时候注意顺序，$$dp(i, S)$$表示当前在点$$i$$，枚举上一个状态是$$S$$，那么有转移

```bash
// 对点重新编号，另外重新赋点权
for i = 1 to n:
	for S = 0 to (1<<colors) 枚举上一个状态
	if dp(i, S) == -1:			continue
	
	if c(i) == -1:		一定要选，dp(i, S) += w(i)
	else:
		如果上一个状态 S 不包含颜色 i，需要把 w(i) 的权值加进来
		if ((S >> c[i] & 1) == 0):		chmax( dp(i, S | (1<<c[i]) ), dp(i, S) + w(i) );
		
	ans = max(ans, dp(i, S))
	枚举下一个点，转移
	for j in G[i]:		chmax(dp(j, S), dp(i, S))
```
算法实现的时候，注意几点，因为要涉及到压状态
点权要先计算，因为原问题给的权值是颜色的权值
另外，因为状态中只保留$$cnt(c_i) \geqslant 2$$的点，所以要对点**重新编号**
对于$$cnt = 1$$的点编号成$$-1$$，在计算$$dp$$的时候特判

>特别注意，因为这里压状态的时候只压$$cnt(c_i) \geqslant 2$$的状态
  所以需要做两件事情，对点重新编号，必要时重新赋点权
 
## ICPC 网络预选赛2 2021 K
**ICPC 网络预选赛2 2021 K. Meal**
有$$n$$个食堂，$$n$$道菜，每个人可以按一定的规则生成一个偏好列表
然后从$$1 \sim n$$，每个人按顺序依次选择偏好列表中，最靠前的，没有被别人选择过的菜
对于所有$$i, j$$，输出第$$i$$个人取到第$$j$$道菜的概率

题中给的数据如下，第$$i$$个人会在还没拿走的菜中随机选一个，拿走第$$j$$个菜的概率是
```math
\displaystyle
\frac{a_{i, j}}{\sum_{k \in S} a_{i, k}}
```

### 算法分析
> 首先来看概率怎么求

最直接的想法，用$$dp(i, S)$$表示，前$$i$$个人，已经选走的菜的集合是$$S$$的概率
那轮到第$$i$$个人来选菜，他还是会以
```math
a_{i, 1} : a_{i, 2}:\cdots :a_{i, m}
```
的比例来选择菜，那么概率如何转移呢？可以在
```math
(a_{i, 1}, a_{i, 2}, \cdots, a_{i, m})
```
中把那些$$\in S$$中的菜都拿走，重新编号，只考虑剩下的菜

> 考虑状态转移，$$dp(i, S) \to i+1$$ 怎么转移

考虑$$dp(i, S)$$，$$i-1$$转移到$$i$$的情况

* 把**当前**不在$$S$$中的元素（没被选过）都拿出来，不妨设这些元素是
  ```math
  a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}
  ```
  并且求出他们的和$$sum$$
  
* `for j = 1 to m`，考虑$$a_{i, j}$$
   ```math
   \displaystyle
   dp(i, S) \cdot \frac{a_{i, j}}{sum} \to dp(i+1, \quad S \mid 2^j )
   ```
   状态转移用的是`+=`
   
### 算法实现
#### 递归方法求逆元

已知$$1^{-1} \equiv 1 (\bmod p)$$，现在要求$$i$$在$$\bmod p$$意义下的逆元$$i^{-1}$$，不放设
```math
\displaystyle
p = ki + j, \quad
\begin{cases}
k = \lfloor \frac{p}{i} \rfloor \\
j = p \bmod i
\end{cases}
```
从而有$$ki + j \equiv 0(\bmod p)$$，两边同时$$\times i^{-1} \cdot j^{-1}$$，得到
$$kj^{-1} + i^{-1} \equiv 0(\bmod p), \quad i^{-1} \equiv -kj^{-1} (\bmod p)$$，将$$k, j$$表达式代入
```math
\displaystyle
i \equiv
\begin{cases}
1 & (i = 1) \\
-\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} & (i > 1)
\end{cases}
(\bmod p)
```

```bash
inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
```

#### 本题算法实现
> 特别注意

状态压缩问题，$$dp(i, S)$$这个状态表示，$$S$$表示的都是，**当前正在进行，还未选择完毕**，对应的状态是$$S$$
所以转移到$$dp(i+1, S')$$的时候，统计答案
答案应该是$$dp(i, S) \cdot prob(i, j)$$，$$prob(i, j)$$表示选择了$$j$$的概率

```bash
int main() {
	//.... 其他代码省略

dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int S = 0; S < (1<<n); S += 1) {
            if (dp[i][S].val() <= 0) continue;

mint sum = 0;
            for (int j = 0; j < n; j++) if ((S >> j & 1) == 0) sum += a[i][j];

mint prob = dp[i][S] * inv[sum.val()];
            for (int j = 0; j < n; j++) if ((S >> j & 1) == 0) {
                dp[i+1][S | (1<<j)] += prob * mint(a[i][j]);
                ans[i][j] += prob * mint(a[i][j]);
            }
        }
    }
	
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d%c", ans[i][j].val(), " \n"[j == n-1]);
        }
    }
}
```

## CCPC Harbin 2021 G
**[CCPC Harbin 2021 G, Damaged Bicycle](https://codeforces.com/problemset/gymProblem/103447/G)**
有$$n$$个点$$m$$条边的无向图，每条边有一个边权
其中$$k$$个点上有自行车，但是有一定概率是坏的，你只有到达那个点才知道自行车是好的还是坏的
你从$$1$$号点到$$n$$号点，步行速度$$w_1$$，骑车$$w_2$$
你要**最小化**到达$$n$$号点的期望时间

### 算法分析
可以先预处理两两间的最短路，存在$$d(i, j)$$中

实际上，我们只需要关心那些有自行车的点，在中途的点停留是没有意义的，把有自行车的点称为**关键点**

> 对于关键点$$u$$，到终点的期望时间怎么求？

实际上，所求的答案就是$$\min (p_0 \cdot T_0 + p_1 \cdot T_1 )$$，$$p_0, p_1$$分别表示自行车是**好的和坏的**概率
它们的值是确定的，只要尝试最小化$$T_0, T_1$$即可

> 如果$$u$$点自行车是好的，怎么求$$T_0(u, n)$$

注意到，如果$$u$$自行车是好的，从$$u \to n$$只需要沿着**最短路径**，骑自行车就可以了
中途在其他的点停留，显然是不忧的（因为骑车更快$$w_2 > w_1$$）
由此，$$T_0 = d(u, n) / w_2$$，所求的答案变为
$$p_0 \cdot \left( d(u, n) /w_2 \right) + p_1 \cdot \min (T_1)$$

> 考虑$$u$$自行车坏了，怎么求$$T_1(u, n)$$

可以有两种决策，第一种是直接步行，那么$$t_0(u, v) = d(u, n) / w_1$$

第二种是枚举中间的**关键点**$$j$$，先步行到**关键点**
然后根据关键点自行车是好还是坏，再继续以$$p_0, p_1$$的概率，走到终点，这就有**状态转移**了
这种情况就可以考虑$$dp$$了，$$dp(u, n)$$表示$$u \to n$$的**最小期望时间**
那么这种决策对应$$t_2(u, v) = \min(\   d(u, j) /w_1 + dp(j, n) \ ) $$

```math
\displaystyle
T_1(u, v) = \min\{ d(u, n)/w_1, \quad \forall j : d(u, j)/w_1 + dp(j, n) \}
```

> 考虑状态压缩优化

实际上，我们在枚举$$j$$这个点的时候，没有必要考虑所有的关键点，如果我们已经访问过某些点，
就可以确定了这些点的自行车是好还是坏，
如果这个点自行车是好的，那么一定会从这个点直接到终点，不会有后续的枚举决策，
只有检查过的点，自行车是坏了的情况，我们才需要后续枚举其他关键点，这样就可以对访问的点**压状态**

记状态$$S$$为访问过的点，且这些点的自行车已经确定是坏的
$$dp(S, i)$$表示当前状态是$$S$$，位于关键点$$i$$，此时到达终点的**最小期望时间**
$$dp(S, i) = p_i \cdot d(i, n) / w_2 + (1-p_i) \cdot \min T(i, n) $$
$$T(i, n)$$表示$$i$$这个点自行车坏了的情况下，到达终点的所需时间

当在$$i$$点的时候，$$S$$中的状态此时应该**考虑过**$$i$$了，有转移（$$p_i$$是车坏的概率）
```math
\displaystyle
dp(S, i) \longleftarrow (1-p_i) \cdot \frac{d(i, n)}{w_2} + \min \begin{cases} d(i, n) / w_1 \\ d(i, j) / w_1 + dp(S \mid 2^j,  j) & j\notin S \end{cases}
```
> 注意到存在$$dp(S \mid 2^j , j) \to dp(S, i)$$的转移，枚举$$S$$的时候从大到小
最后计算答案的时候，实际上同样，要么是从起点走路到终点，要么是找一个关键点，走路到关键点，然后骑车到终点

计算答案时候，是$$\min( d(s, t)/w_1, \quad \min_j d(s, j)/w_1 + dp(1\ll j, j) )$$

### 算法实现
```bash
int main() {
	// 预处理两点间的最短路
	// 对 K 个关键点重新编号 0-K
	// 起点编号 K，终点编号 K+1，两点间的最短路用 d[i][j] 表示
	
    if (d[K][K+1] >= inf) {
        puts("-1");
        return 0;
    }

for (int S = bit(K) - 1; S >= 0; S--) {
        for (int i = 0; i < K; i++) if (S & bit(i)) {
            double pbad = 0.01 * p[i];
            double pgood = 1 - pbad;

double tgood = 1. * d[i][K+1] / v2;
            double tbad = 1. * d[i][K+1] / v1;
            for (int j = 0; j < K; j++) if ((S & bit(j)) == 0) {
                chmin(tbad, 1. * d[i][j] / v1 + dp[S | bit(j)][j]);
            }

dp[S][i] = pgood * tgood + pbad * tbad;
        }
    }

double ans = 1. * d[K][K+1] / v1;
    for (int j = 0; j < K; j++) {
        chmin(ans, 1. * d[K][j] / v1 + dp[bit(j)][j]);
    }
	
}
```

## CCPC Changchun 2020 J
**[CCPC Changchun 2020 J, Abstract Painting](https://codeforces.com/gym/102832/problem/J)**
画家画圆，要满足以下条件
* 圆心必须是整数点

* 圆上任意点坐标必须$$\in [0, n]$$范围内

* 圆的半径必须是一个不超过$$5$$的正整数

* 任何两个圆最多只能有一个交点

画上已经有$$K$$个圆了，现在画家可以什么都不画，或者画一个或者多个圆，下面问能够得到多少种不同的画

### 算法分析
圆在这个问题中，可以看作若干条线段
假设从$$i$$开始，在$$[i, n]$$画若干条线段，线段和线段之间**只能在端点相交**
这样的线段问题，可以尝试**区间 dp**，$$dp(l, r)$$表示在$$[l, r]$$中画线段的方案数

>  这种问题有一点像括号匹配问题，括号匹配问题一般如下处理
需要记两个东西，第一就是一整段都匹配上的方案数，记为$$dp(l, r)$$，第二就是没有限制的情况，记为$$g(l, r)$$

*  假设一整段匹配上了，计算$$dp(l, r)$$

*  假设这一段没有限制，计算$$g(l, r)$$，首先$$g(l, r) \leftarrow dp(l, r)$$
   然后枚举中间情况，一般假设$$l$$和某一个位置$$m \in [l, r]$$匹配，然后转移
   $$g(l, r) \leftarrow dp(l, m) \cdot g(m+1, r)$$
   
**这个问题也类似**
$$dp0(l, r)$$表示$$[l, r]$$之间一定没有线段，$$dp1(l, r)$$表示$$[l, r]$$之间一定有线段（即一定有一个圆）

* 对于$$dp0(l, r)$$，我们有
  ```math
  dp0_{l, r} \leftarrow dp0_{l+1, r} + dp1_{l+1, r} \\
  \textbf{for } \ \forall m \in [l+2, r]: dp0_{l, r} \leftarrow dp1_{l, m} \cdot (dp1_{m, r} + dp0_{m, r})
  ```

* 对于$$dp1(l, r)$$，如果满足$$r-l \leqslant 10$$并且$$r-l$$是偶数，那么
  $$dp1(l, r) \leftarrow dp0(l, r)$$
  
* 另外，这个问题中，因为原来就存在一些圆，计算完成之后，要修改一些决策
  如果$$[l, r]$$之间本来就有一个圆，那么要令$$dp0(l, r) = 0$$
  因为我们考虑 dp 的时候，是不考虑原来条件的限制的，限制条件最后再加上
  
### 算法分析：状态压缩
![](/media/content_img/statusdp01.png)

对于$$i \in [0, n]$$，每个$$i$$只需要考虑$$5$$个点就可以了，$$(i, i-2, i-4, \cdots, i - 10)$$
实际上，对于每个$$i$$而言，它能影响的点有$$10$$个，最坏的情况，$$(i, i - 10)$$画一个圆（连一条边）
那么$$i-1, i-2, \cdots, i - 9, i - 10$$都不可以往后连了
> 这里说的不能往后连，是考虑对于$$> i$$的点作为**右端点**，即$$i \to i+1$$时，
   $$i-1, i-2 \cdots i - 10$$都**不可以作为左端点了**
   
这样就可以考虑状态压缩了，对于当前的点$$i$$，对连边的情况压状态，记一下往后的过程中（$$i \to i+1$$）
哪些点可以作为左端点继续往后连，哪些点不可以再往后连了
用$$dp(i, S)$$表示这样的方案数，下面考虑状态转移

对于点$$i$$，状态位$$(0, 1, \cdots, 9) \longleftrightarrow (i-1, i-2, \cdots, i -10)$$
状态位是$$1$$表示可以继续往后连（即作为左端点），状态位是$$0$$表示不能继续连了

对于$$j \in (i-2, i-4, \cdots, i-10)$$，考虑$$j, i$$之间要不要连（即画不画圆）？
如果`used(j, i) = 0`，那么$$j, i$$**连不连都可以**
否则的话，$$j, i$$之间一定要连

> 对每个 $$j$$ 考虑内部状态转移

对于不连的情况，$$dp(i+1, S) \leftarrow dp(i, S)$$
对于$$j, i$$相连的情况，$$i-1, i-2, \cdots, i-k$$这些位都要置为$$0$$，实际上对应状态压缩是
$$(0, 1, \cdots, k-1)$$这些位，要将这些位都设置成$$0$$，剩下的位不变

实际上，$$i - k = j$$，也就是说$$(0, 1, \cdots, i-j-1)$$这些位都设置成$$0$$，一共有$$10$$位二进制位
新的状态是$$S \textbf{ and } (2^{10} - 2^{i-j-1})$$

> 考虑$$i \to i+1$$的状态转移

枚举$$S \in [0, 2^{10}]$$所有的状态，$$dp(i+1, nS) \leftarrow dp(i, S)$$，那么$$nS$$如何求呢？
就要考虑$$S \to nS$$是怎么变化的，除了首尾两个位，其他位都保持不变

令$$(S \ll 1 \textbf{ or } 1)$$，表示新加进来的$$i+1$$位一定可以向后连
左移$$1$$位，表示最高位不要了，然后$$\textbf{ or }$$上一个$$1$$，表示新加进来的位一定可以向后连
其他位保持不变，所以$$nS \leftarrow (S \ll 1 \textbf{ or } 1) \textbf{ and } (2^{10} - 1)$$

**特别注意**
在$$i \to i+1$$递推到下一个阶段的时候，原来$$S$$的 dp 值，对应$$(S \ll 1 \textbf{ or } 1) \textbf{ and } (2^{10} - 1)$$的 dp 值

```bash
int main() {
	// ....
	
    vector<mint> dp(maxn, 0), last(maxn, 0);
    dp[0] = 1;

for (int i = 0; i <= n; i++) {
        for (int j = i-2; j >= 0 && i - j <= 10; j -= 2) {
            last = dp, dp = vector<mint> (maxn, 0);

if (!used[j][i]) {
                for (int S = 0; S < bit(10); S++) dp[S] = last[S];
            }

for (int S = 0; S < bit(10); S++) if (S & bit(i-j-1)) {
                int nS = S & (bit(10) - bit(i-j-1));
                dp[nS] += last[S];
            }
        }

last = dp, dp = vector<mint> (maxn, 0);
        for (int S = 0; S < bit(10); S++) {
            int nS = ((S << 1) | 1) & (bit(10) - 1);
            dp[nS] += last[S];
        }
    }
    mint ans = 0;
    for (int S = 0; S < bit(10); S++) ans += dp[S];
    printf("%d\n", ans.val());
}
```

上一篇：状态压缩动态规划（一）下一篇：轮廓线动态规划

看完文章有啥想法