计数动态规划

[[ slider_text ]]

[[ item.c ]]

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

dp计数

## ICPC Shanghai 2021 G
**[ICPC Shanghai 2021 G, Edge Groups](https://codeforces.com/gym/103446/problem/G)**
**问题描述**
有一棵$$n$$个点$$n-1$$条边的树，其中$$2 \mid (n-1)$$，把这些边分成$$(n-1)/2$$组
使得每条边在一个组里面，并且每个组的两条边有一个公共端点，可以理解为每一组是一条长度为$$2$$的路径

### 算法分析
注意到如果一个点的子树中，有偶数条边，那么**子树内部**就可以完成匹配了
否则就必然存在一条**伸出来的边**，要和父亲节点匹配
![](/media/content_img/countdp-01.png)

如图所示，如果$$u$$的儿子$$v$$，它所在的子树有偶数条边，那么只需要考虑**分支边**$$(u, v)$$
如果有奇数条边，那么连接儿子的**分支边**要**合并到儿子中去**，转换成偶数边的情况
考虑$$u$$的时候不计算这条分支边

对每个点统计答案，假设当前统计$$u$$

*  如果$$u$$有偶数条分支边，那么这些分支边都可以直接匹配

*  否则有奇数条分支边，那么需要和连向祖先的边$$(u, pa_u)$$**合并**
   之后回溯到祖先$$pa_u$$的时候，$$u$$是作为一个奇儿子来考虑的，$$(u, pa_u)$$这条边不会再被统计了
   
*  这样所有的情况都可以转换成偶数的情形，假设当前有$$(2k)$$个分支边
   那么对于第一条未匹配的边，有$$(2k-1)$$种选择，第一轮匹配了$$2$$条边，剩下$$(2k-2)$$条边
   然后再选第一条未匹配的边，有$$(2k-2-1)$$种选择，以此类推
   对于每个点的答案是$$(2k-1)!! = (2k-1) \cdot (2k-3) \cdots 3 \cdot 1$$
   
## ICPC EC Final 2020 A
**[ICPC EC Final 2020 A, Namomo Sequence](https://codeforces.com/gym/103069/problem/A)**
**问题描述**
给定一个$$10^6$$的字符串，问有多少个namomo子序列（子序列中字符不一定要求连续）
namomo子序列满足以下条件
* 长度是$$6$$

* 找出下标是$$t_1, t_2, \cdots, t_6$$构成子序列，子序列有形式`ABCDCD`
  `ABCD`是不同的，但是子序列`sub[3] = sub[5] = C,   sub[4] = sub[6] = D`
  子序列的第`3, 5`个字符必须相同，`4, 6`也必须相同
  
### 算法分析
最简单的，枚举`ABCD`分别是哪些字母
然后考虑原串的第$$i$$个位置，匹配上第$$j(1 \leqslant j \leqslant 6)$$位，方案数记为$$dp(i, j)$$
这样做的复杂度是$$O(n |\Sigma|^4)$$

反过来想，实际上我们只要枚举`CDCD`，枚举`C`是哪个，`D`是哪个，然后再在前面放上两个不同于`C D`的字母
这样就可以把复杂度降到$$O(|\Sigma|^2)$$

> 怎么设计 dp 状态

设计 dp 状态的思路，和普通的匹配问题差不太多。$$dp(i, j)$$表示对于原串第$$i$$个位置，已经匹配上了$$j$$个字符
$$j \in [0, 6]$$，实际上，形如`ABCDCD`的串，`AB`是任意的，`CDCD`是相对确定的
如果枚举计算出形如`CDCD`的方案数，可以直接计算出`AB`的方案数

> 假设已知形如`CDCD`的方案数，如何计算出`AB`的方案数

我们可以统计原串中，**可供使用的字符**的个数，只要一个字符在前缀中出现过，就认为它可供使用
从这些字符中选 2 个不同的，填到`AB`这两个位置上，不放设`cnt[x]`表示`x`出现的次数
方案数可以记为
```math
\displaystyle \sum_{ i \neq j, i \neq CD, j \neq CD } (cnt_i \cdot cnt_j) / 2
```
这个数学表达式的求解实际上并不复杂，考虑
```math
\displaystyle
\sum_i\sum_{j, j \neq i} a_i \cdot a_j = \left(\sum_i a_i \right) \cdot \left( \sum_j a_j \right) - \sum_i (a_i ^2) \\

=\left(\sum_i a_i \right)^2 - \sum_i a_i ^2
```
从而，我们可以直接求出`AB`的方案数，不妨记$$\sum_i a_i = S$$，记$$\sum_i a_i^2 = S2$$
```math
\displaystyle
res = (S - cnt_C - cnt_D)^2 - (S2 - cnt_C^2 - cnt_D^2) 
```

> 那么如何求`CDCD`的方案数？

注意到，我们只需要关注有几个形如`CDCD`的段，另外还需要**枚举字符集**，可以把`C D`也记录到状态中
**从后往前 dp** 即可

`dp [i] [0/1/2/3] [C] [D]` 来表示方案数，即当前考虑原串中$$i$$这个位置，匹配了`CDCD`中`0/1/2/3`个位
原串中最后的位置$$i$$的字符是`C`，我们枚举了（填上了）字符`D`，$$C \neq D$$，那么有转移

$$dp(i, 0, C, D) \to dp(i-1, 1, C, D)$$

$$dp(i, 2, C, D) \to dp(i-1, 3, C, D)$$

$$dp(i, 1, D, C) \to dp(i-1, 2, D, C)$$

最后 $$dp(i-1, 3, D, C)$$表示一个`CDCD`段匹配结束了，可以进入下一个段，需要**统计答案**
上面已经算出来能够选择`AB`的方案数是$$res$$，所以要把$$dp(i-1, 3, D, C) \cdot res$$加到答案中

> 但这样做的话，空间开不下，怎么优化呢？

可以考虑用**滚动数组**，省去$$i$$这一维，那么如何计算$$res$$呢？

预处理的时候，先把所有的`cnt`值都加入`S, S2`中
从后往前倒着做，**边滚动边维护**，加入一个字符`x`，$$S$$和$$S2$$怎么变化的呢？
假设说当前加入一个字符`x`
`S`是所有字符个数的统计，所以`S = S + 1`，同时`cnt[x] += 1`
`S2`统计的是$$cnt_x^2$$，那么要减去旧的加上新的，$$S2 \leftarrow S2 - (cnt_x-1)^2 + cnt_x^2$$
`S2 = S2 + 2 * cnt[x] - 1`，这样就可以维护$$res$$了

具体来说，先预处理整个串，加入整个串的字符，
倒着往前扫描原串，不放设当前考虑的位置是$$i$$，先要把$$s_i$$从字符集中删去
因为接下来$$s_i\cdots s_n$$这些后缀字符**都不能继续使用**，同时维护出$$S, S2$$（这些就是能够**供我们使用**的字符集）
然后进行 dp 的转移

### 算法实现
```bash
ll sum, sum2;
vector<ll> cnt(M+5, 0);
inline void add(int x) {
    sum += 1;
    cnt[x] += 1;
    sum2 += 2 * cnt[x] - 1;
}

inline void del(int x) {
    sum -= 1;
    sum2 -= 2 * cnt[x] - 1;
    cnt[x] -= 1;
}

inline int query(int C, int D) {
    ll res = 1LL * (sum - cnt[C] - cnt[D]) * (sum - cnt[C] - cnt[D])
        - (sum2 - cnt[C] * cnt[C] - cnt[D] * cnt[D]);

return res / 2 % P;
}

int main() {
    n = str.size();

for (int i = 0; i < n; i++) add( decode(str[i]) );

vector<vector<vector<mint> > > dp(4, vector<vector<mint> > (M+5, vector<mint> (M+5, 0)));

for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) if (i != j) dp[0][i][j] = 1;
    }

mint ans = 0;

for (int i = n-1; i >= 0; i--) {
        auto C = decode(str[i]);
        del(C);

for (int D = 0; D < M; D++) if (D != C) {
            dp[1][C][D] += dp[0][C][D];
            dp[3][C][D] += dp[2][C][D];
            dp[2][D][C] += dp[1][D][C];

ans += dp[3][D][C] * mint( query(C, D) );
        }
    }

printf("%d\n", ans.val());
}
```

## ICPC SEERC 2020 I
**[ICPC SEERC 2020 I, Modulo Permutations](https://codeforces.com/gym/103102/problem/I)**
**问题描述**
给定一个$$1 \sim n$$的排列，环形，要求满足对每个$$i$$，有$$p\_i \bmod p\_{i+1} \leqslant 2$$
问满足条件的排列的方案数

### 算法分析
首先可以打表找规律，可以发现，$$1, 2$$这两个数是没有限制的
因为不论$$p\_i = (1, 2)$$还是$$p\_{i+1} = (1, 2)$$，上述性质都可以满足
![](/media/content_img/countdp-02.png)

问题就转换成为，对$$3\sim n$$这些数分成`2`组，要求新加入的数`new`，和当前的数`x`满足
$$\text{new} \bmod x \leqslant 2$$ 成立

$$dp(i, j)$$表示这两个组，最后（即当前）放进来的数分别是$$i, j$$，其中$$j < i$$，所对应的方案数

考虑转移，假设要新加入$$i+1$$，有如下两种情况

* $$i+1$$加入$$i$$这个组，因为$$(i+1) \bmod i < 2$$恒成立，有转移$$dp(i, j) \to dp(i+1, j)$$

* $$i+1$$加入$$j$$这个组，必须满足$$(i+1) \bmod j \leqslant 2$$，才有转移$$dp(i, j) \to dp(i, i+1)$$

> 打表的性质怎么证明

注意到，因为不论是$$p\_i = \\{1, 2\\}$$还是$$p\_{i+1} = \\{1, 2 \\}$$，都不违背$$p\_{i} \bmod p\_{i+1} \leqslant 2$$
不管你另一个数取什么数，都不违背，所以$$1, 2$$是没有限制的

那么考虑其他数，不妨设$$x, y \in [3, n], x < y$$，如果按$$(x, y)$$这样**递增排列**，那么$$x \bmod y = x > 2$$，就不满足了

所以一旦确定了一个组里要放哪些数，那么排列的方法是**唯一确定**的，要按**递减顺序**排列
于是 dp 的过程，就是对$$3 \sim n$$分组的方案数

> 还可以优化吗

注意到分成两个组，这两个组之间**没有特殊的要求**
可以定义$$dp(i, j)$$表示放入两个组最后的元素分别是$$i, j$$，其中$$j < i$$，这样就存在转移
$$dp(i, j) \to dp(i+1, j)$$
$$dp(i, j) \to dp(i+1, i), \quad (i+1) \bmod j \leqslant 2$$
这样可以滚动数组优化掉第一维，我们令$$j < i$$
第一种转移，是 dp 数组直接复制，不需要额外操作
第二种转移，实际上`dp[i] += last[j]`，而这里`last[j]`是直接复制上一阶段的`dp`值
所以可以**直接写成**`dp[i] += dp[j]`

另一方面，注意到限制条件，$$(i+1) \bmod j \leqslant 2$$，也就是说，有以下情况
$$j \mid (i-1), j \mid i, j \mid (i+1)$$
这样可以预处理因子，枚举$$i$$的时候，也枚举$$(i-1), i, (i+1)$$对应的因子，这样复杂度是$$O(n \log n)$$的

如果想要常数更好一点，可以知道，枚举倍数比枚举因子简单
可以先枚举$$j$$，然后再依次枚举$$j$$的**倍数**$$i$$，检查$$i-1, i, i+1$$，然后转移

另外，还注意到如果$$j \mid (i-1), j \mid (i+1)$$，那么有
$$j \mid \textbf{gcd}(i-1, i+1) \Longrightarrow j \mid (2, i-1) \Longrightarrow j \mid 2$$
于是$$j \leqslant 2$$，也就是说，如果$$j > 2$$，那么$$j \mid i, j \mid (i-1), j \mid (i+1)$$只会满足其中一个

注意到，限制条件是$$(i+1) \bmod j \leqslant 2$$，那么如果$$j \leqslant 3$$，不管$$i$$取什么数都满足条件
因为$$\bmod 3$$肯定$$\leqslant 2$$，所以只考虑$$j \geqslant 4$$情况，那么就有
$$j$$只能整除$$i-1, i, i+1$$其中一个，那么挨个枚举就可以了

### 算法实现
```bash
int main() {
    // ....
    vector<vector<int> > d(n+1, vector<int>());
    for (int j = 1; j <= n; j++) {
        for (int i = j; i <= n; i += j) d[i].push_back(j);
    }

// dp[2][1] = 1
    vector<mint> dp(n+1, 0);
    vector<int> vis(n+1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n-1; i++) {
        for (int x = i-1; x <= i+1; x++) for (auto j : d[x]) {
            if (vis[j] == i || j >= i) continue;
            vis[j] = i;

dp[i] = dp[i] + dp[j];
        }
    }

mint ans = 0;
    for (int j = 1; j < n; j++) ans += dp[j];
    ans *= n;

printf("%d\n", ans.val());
}

// 实现2
int main() {
    vector<mint> dp(n+1, 0);
    dp[1] = 1;

for (int j = 1; j <= n-1; j++) {
        if (j <= 3) {
            for (int i = j+1; i <= n; i++) dp[i] += dp[j];
        }
        else {
            for (int d = -1; d <= 1; d++) {
                for (int i = j+d; i <= n; i += j) if (i > j) {
                    dp[i] += dp[j];
                }
            }
        }
    }
    mint ans = 0;
    for (int j = 1; j < n; j++) ans += dp[j];
    ans *= n;
    printf("%d\n", ans.val());
}
```

## ICPC SEERC 2020 F
**[ICPC SEERC 2020 F, Fence Job](https://codeforces.com/gym/103102/problem/F)**
**问题描述**
给定一个$$1\sim n$$的排列，可以进行若干次操作，每次操作选一个区间$$[l, r]$$
把区间内的数都改成$$\min [l, r]$$，通过多次操作（可以是`0`次），能够得到多少种不同的设计？
$$A, B$$是不同的设计，只要有一个位置$$i$$满足$$A_i \neq B_i$$

### 算法分析
![](/media/content_img/countdp-03.png)

注意到原序列是一个**排列**，并且只能**从小到大扩展，小的数覆盖大的数**，那么有如下性质

**性质一**
如果$$a_l = x, a_r = x$$，那么$$[l, r]$$之间的数也必然都是$$x$$，这个不难证明

首先，$$[l, r]$$中的数如果$$< x$$，我们只能**从小的值往大的值扩展，小的值覆盖大的值**
因此，如果中间有一个**较小的值 gap**，另一侧的$$x$$是扩展不过来的
另一方面，因为原序列是一个排列，所以最开始只有一个$$x$$，要在另一个位置出现$$x$$，只能**扩展**
所以，这两个位置**中间的值都$$ > x$$**，这样操作下来，**中间的值都被$$x$$抹平了**

综上所述得出一个**结论**
如果$$a_l = x, a_r = x$$，那么$$[l, r]$$连续的一段值都是$$x$$
 
**推论一**
根据这个性质，我们可以简单写一个 dp，假设原序列是$$h$$，变换后是$$a$$
$$dp(i, j)$$表示变换后，$$a_i$$由$$h_j$$向右扩展得到（$$j < i, \ h_j = a_i$$）
那么显然，此时有$$h_i \geqslant h_j$$（对于$$j > i$$的情况是对称的）

这启发我们考虑$$i \in [1, n]$$每个位置，变换后得到的$$a_i$$，它是由哪些位置扩展而来的？
$$dp(i, j)$$表示变换后新序列$$i$$这个位置，是由$$j$$扩展而来，即$$a_i \leftarrow h_j$$

那么有转移 $$dp(i, j) = \displaystyle \sum_x dp(i-1, x)$$，但是$$x$$是有限制的，首先$$x < i$$
另外再想上图所示的那个问题，这时$$j$$和$$x$$要**满足什么条件？考虑最终序列的状态**

* $$h_x$$一定是$$[x, i-1]$$区间的最小值

* 若有$$j:\  x \leqslant j < i$$，那么一定有$$h_j \geqslant h_x$$，否则$$x$$**扩展不到**$$i-1$$处

* 若有$$j: j < x$$，那么$$j$$要想扩展到$$i$$，一定要满足$$h_j \leqslant h_x$$
  换句话说，$$h_j$$是$$[j, i]$$区间内的**最小值**，但是，在$$j \to i$$扩展的过程中，
  **会覆盖了$$i-1$$处的值**，$$i-1$$处的最终的值是从$$j$$处过来的，而不是从$$x$$扩展过来的
  这种情况不计入在内，我们只关心最终序列，每个位置是从哪里扩展过来的，否则会重复计算
  **具体重复计算的情况，见上图**
  
**结论**
$$dp(i, j) \leftarrow \sum_x dp(i-1, x)$$，$$x$$必须满足
$$x \leqslant j < i, \ h_x \leqslant h_j$$

**性质二**
对于$$x < i$$
```math
\displaystyle
dp(i, j) = \sum_{x: \ x \leqslant j, h_x \leqslant h_j} dp(i-1, x)
```
可以写成
```bash
for x = 0 to j:
	dp(i, j) = dp(i-1, 0)[ h(0) 是 [0, i] 的最小值 ] + dp(i-1, 1)[ h(1) 是 [1, i] 的最小值 ] + ...
		+ dp(i-1, j)[ h(j) 是 [j, i] 的最小值 ]
	// [...] 表示布尔条件
```

> 怎么优化？

$$dp(i, j)$$要为合法状态，那么$$h_j$$就必须是$$[j, i]$$区间的**最小值**
注意到$$x \leqslant j \leqslant i-1$$，$$dp(i-1, x)$$为合法状态，$$h_x$$就一定是$$[x, i-1]$$的最小值
$$h_x \leqslant h_j \leqslant h_i$$，即$$h_x$$是区间$$[x, i]$$的最小值（对应上述伪代码布尔条件为真）
当且仅当 **dp 值对应合法状态**

我们在 dp 的时候，如果状态不合法，比如最小值不是$$h_x$$，dp 值直接就置为 0
只在合法的时候转移，这样就可以用前缀和来求 $$\sum_x dp(i-1, x)$$

```bash
dp(i-1, 0)[ h(0) 是 [0, i] 的最小值 ] + dp(i-1, 1)[ h(1) 是 [1, i] 的最小值 ] + ...
        + dp(i-1, j)[ h(j) 是 [j, i] 的最小值 ]
		
		= dp(i-1)[1...j] 的前缀和 sum(j)

这一可以在遍历每个 i 的时候预处理
```
这样复杂度就是$$O(n^2)$$的了
```bash
for i = 1 to n:
	预处理前缀和，sum(j) = dp(i-1)[1...j] 的前缀和
	for j = 1 to n:
		if h(j) 是 [j...i] （或者 [i...j]）间的最小值：	dp(i, j) = sum(j)
```

## CCPC Mianyang 2020 B
**[CCPC Mianyang 2020 B, Building Blocks](https://codeforces.com/gym/102822/problem/B)**
**问题描述**
给定一个积木，定义左前视图，即从左下角$$40$$度方向看过去，投影取划分成的小三角形高度的最大值
俯视图有$$n$$行$$m$$列，每一个方块必须至少放置 1 个积木
左前视图有$$n+m$$列，给定这些列，每一列的高度是多少
还有额外$$k$$个条件，知道俯视图坐标$$(x_i, y_i)$$处有$$h_i$$的高度

剩下的高度$$\geqslant 1$$的整数，但你可以自己定，必须满足以上限制
问有几种不同的方案数

### 算法分析
![](/media/content_img/countdp-04.png)

考虑朴素的做法，不妨考虑$$dp(i, j)$$，第$$i$$条对角线，有$$f_i = j$$（其中$$f_i$$表示对角线经过的方格的最大值）

如果$$f\_{i+1} = k$$，那么满足以下条件
$$a\_{i+1} = \max(f\_i, f\_{i+1}) =\max(j, k)$$，另外考虑$$f\_{i+1} = k$$的方案数

> 先看$$f\_{i+1} = k$$这条对角线，假设对角线上已知的最大值是$$h$$，剩下$$c$$个位置未填

*  如果$$h > k$$，方案数是$$0$$

*  如果$$h = k$$，剩下只需要填$$c$$个$$\leqslant h$$的数即可，方案数是$$h^c$$

*  如果$$h < k$$，那么需要在剩下的位置**至少有一个填$$k$$**，且剩下的数都要$$\leqslant k $$
   方案数是$$k^{c} - (k-1)^c$$
   
>  再考虑 dp 的转移

$$\max(j, k) = a\_{i+1}$$，肯定不能全部遍历$$i, j$$，这样会超时
考虑$$dp(i, j) \to dp(i+1, k)$$，即$$i \to k$$是怎么变化的，有什么关系？
他们的关系受到$$a\_{i+1}$$限制，而$$a\_{i+1}$$是已经给定的，可以分类讨论

*  如果$$j = a\_{i+1}$$，那么$$k$$可以取任意$$\leqslant a\_{i+1}$$的数

*  如果$$j \neq a\_{i+1}$$，那么$$k = a\_{i+1}$$

从而根据$$j \neq a\_{i+1}$$，确定$$j$$这一维是$$0/1$$，不放设$$dp(i, 0)$$表示$$j < a\_{i+1}$$
$$dp(i, 1)$$表示$$j = a\_{i+1}$$，接下来考虑转移

$$dp(i, 0)$$，表示$$j < a\_{i+1}$$，
那么$$k = a\_{i+1}$$，看$$a\_{i+1} < a\_{i+2}$$还是$$a\_{i+1} = a\_{i+2}$$，转移到$$dp(i+1, 0/1)$$.

$$dp(i, 1)$$，那么此时$$j = a\_{i+1}, k \leqslant a\_{i+1}$$，同样考虑$$k = a\_{i+2}$$还是$$k \leqslant a\_{i+2} - 1$$ 来转移

### 算法实现
这个问题的核心有两个
第一是对角线所经过的区域的最大值，考虑根据对角线来 dp，$$dp_i$$记录第$$i$$条对角线
第$$i$$条对角线经过区域最大值记为$$f_i$$

第二是$$a$$取值对$$f$$的限制，$$\max(f\_{i}, f\_{i+1}) = a\_{i+1}$$

注意到我们一开始时候一定有$$a\_0$$是确定的，并且$$a\_0 = f\_0$$
$$a\_1 = \max (f\_0, f\_1)$$，不难发现$$a\_1 \geqslant a\_0$$恒成立
类似的，$$\max(f\_{i}, f\_{i+1}) = a\_{i+1}, \  \max(f\_{i+1}, f\_{i+2}) = a\_{i+2}$$，也就是说
考虑第$$i$$条对角线，它的值$$f$$受到后面的$$a\_{i+1}$$的约束

`dp(i,    f[i] 与 a[i+1] 的关系？)`进行转移，具体来说
`dp(i,    f[i] 与 a[i+1] 的关系) * (第 i+1 条对角线填什么数的方案数) = dp(i+1,   f[i+1] 与 a[i+2] 的关系)`

转移的时候考虑两个问题，`f[i] 与 a[i+1] 的关系？判断 f[i+1] 能填上哪些数？方案数是？`
还有就是`f[i+1] 填上这些数之后，和 a[i+2] 的关系`

* 考虑$$dp(i, 0)$$，首先有$$\max(f\_i, f\_{i+1}) = a\_{i+1}$$，另外根据 dp 的定义，我们有
  $$f\_{i} < a\_{i+1}, \ f\_{i+1} = a\_{i+1}$$，从而我们可以推出
  $$\max(f\_{i+1}, f\_{i+2}) = \max(a\_{i+1}, f\_{i+2}) = a\_{i+2}$$，限制条件是
  **当且仅当**$$a\_{i+2} \geqslant a\_{i+1}$$
  > 接着看$$f\_{i+1}$$与$$a\_{i+2}$$的关系进行转移，而我们推出$$f\_{i+1} = a\_{i+1}$$，就只要看$$a\_{i+1}$$与$$a\_{i+2}$$的关系即可
  
  如果$$a\_{i+1} = a\_{i+2}$$，那么`dp(i, 0) * ( f[i+1] = a[i+1] 的方案数 ) = dp(i+1, 1)`
  如果$$a\_{i+1} < a\_{i+2}$$，那么`dp(i, 0) * ( f[i+1] = a[i+1] 的方案数 ) = dp(i+1, 0)`

* 考虑 $$dp(i, 1)$$，那么我们有$$f\_{i} = a\_{i+1}$$，可推出$$f\_{i+1} \leqslant a\_{i+1}$$，**任意**满足的即可
  > 考虑转移到$$dp(i+1, 1), dp(i+1, 0)$$要满足什么限制？
  
  如果转移到$$dp(i+1, 1)$$，那么我们有$$f\_{i+1} = a\_{i+2}$$成立，充要条件是$$a\_{i+1} \geqslant a\_{i+2}$$
  `限制条件 a[i+2] <= a[i+1]:		dp(i, 1) * ( f[i+1] = a[i+2] 的方案数 ) = dp(i+1, 1)`
  
  如果转移到$$dp(i+1, 0)$$，那么注意到$$f\_{i+1}$$可以是$$\leqslant a\_{i+1}$$的任意数
  $$\max(f\_{i+1}, f\_{i+2}) = a\_{i+2}$$，也就是说我们要满足
  $$f\_{i+1} \leqslant a\_{i+2} - 1, f\_{i+1} \leqslant a\_{i+1}$$，限制条件是$$f\_{i+1} \leqslant \min(a\_{i+1}, a\_{i+2} - 1)$$
  `dp(i, 1) * ( f[i+1] <= min(a[i+1], a[i+2]-1) 的方案数 ) = dp(i+1, 0)`
  
最后就是关于方案数如何计算，我们可以预处理出每一条对角线上有几个位置没有填
假设第$$i$$条对角线有$$c(i)$$个空位，对角线的最大值记为$$f_i$$，已知的最大值记为$$g_i$$

计算$$f_i = x$$的方案数，如果题中给出的已知的最大值$$g_i = x$$，那么剩下位置$$\leqslant x$$的数随便填
答案是$$x^{c(i)}$$
如果题中给出的最大值$$< x$$，那么剩下位置**至少要有一个**$$x$$，答案是$$x^{c(i)} - (x-1)^{c(i)}$$

计算$$f_i \leqslant x$$的方案数，那么就没什么限制了，直接$$\leqslant x$$的数随便填，$$x^{c(i)}$$

```bash
int main() {
	//.... 其他代码省略
    function<mint(int, int)> calceq = [&](int i, int x) -> mint {
        // calc f[i] max = x
        if (f[i] > x || x <= 0) return 0;
        if (f[i] == x) return mint(qpow(x, cnt[i], P));
        return mint(qpow(x, cnt[i], P)) - mint(qpow(x-1, cnt[i], P));
    };
    function<mint(int, int)> calcleq = [&](int i, int x) -> mint {
        // calc f[i] max <= x
        if (f[i] > x || x <= 0) return 0;
        return mint(qpow(x, cnt[i], P));
    };

// dp
    if (a[0] > a[1]) {
        ans = 0;
        return;
    }
    vector<vector<mint> > dp(n+m+1, vector<mint>(2, 0));
    dp[0][a[0] == a[1]] = calceq(0, a[0]);
    // debug(dp[0][a[0] == a[1]].val());

for (int i = 0; i < n+m-2; i++) {
        if (a[i+2] >= a[i+1]) {
            auto res = calceq(i+1, a[i+1]);
            dp[i+1][a[i+1] == a[i+2]] += dp[i][0] * res;
        }
        if (a[i+1] >= a[i+2]) {
            auto res = calceq(i+1, a[i+2]);
            dp[i+1][1] += dp[i][1] * res;
        }
        auto res = calcleq(i+1, min(a[i+1], a[i+2]-1));
        dp[i+1][0] += dp[i][1] * res;
    }
    ans = dp[n+m-2][1];
}
```

上一篇：轮廓线动态规划已经是最后一篇啦

看完文章有啥想法