codeforces上的dp题（一）

[[ slider_text ]]

[[ item.c ]]

codeforces上的dp题（一）

发布时间 2024-10-12 作者：swingmoon 来源：算法小站

mex dp

## Codeforces Round 968 (Div. 2)
**[Codeforces Round 968 (Div. 2) D1. Turtle and a MEX Problem (Easy Version)](https://codeforces.com/problemset/problem/2003/D1)**
**问题描述**
给定$$n$$个序列，第$$i$$个序列的长度为$$l_i$$，记为`ai[1, 2, ..., li]`
现在你要玩一个游戏，给你一个非负值$$x$$，你可以进行如下操作若干次
选择一个$$i$$，令`x = mex(ai[1....li])`，问若干次操作之后$$x$$的最大值变成多少？
这个问题比较简单，现在给一点限制，定义$$f(k)$$表示一开始$$x = k$$时候的答案
现在给你一个值$$m$$，求解
```math
\sum_{i = 0}^{m}f(i)
```

### 算法分析
> 先考虑和第$$i$$个序列进行操作

mex 问题还是考虑填空，能不能补上相应的空缺？用 `vis` 表示一个数是否出现
找到第一个`vis = 0`的数`j1`，第二个`vis = 0`的数`j2`，那么对于$$x$$
如果`x = j1`，那么 `x = mex(x, ....)`，可以发现`x = j2`，这是最大值了，不可能再增加了

否则，若`x < j1`，那么答案就是`x = mex(x,...) = j1`
神奇的是你还可以进行一次操作，令`x = j2`，接着就不能再增加了

若`x > j1`，那么同样你可以进行一次`mex`操作，令`x = j1`，然后再来一次，令`x = j2`
所以接着就需要分析`x`和`j2`哪个大

>  考虑`x`和`j2`的关系

如果`x < j2`，那么可以先一次操作，把`x`变成`j1`，然后再来一次，把`x`变成`j2`
所以对于$$x \in [0, j2-1]$$，答案都是`j2`

如果`x = j2`呢？明智的选择是不需要操作，答案是`x`

如果`x > j2`呢？不需要操作了，也就是说$$x \in [j2+1, m]$$，答案都是`x`本身

综上所述，所求的值为$$j2\cdot j2 + (m+j2)\cdot (m-j2+1) / 2$$
这是一次操作所能取到的最大值，可以发现它仅仅与$$j2, m$$有关，$$m$$已知

于是我们考虑$$j2$$能取什么样的值，不妨设第$$i$$个序列对应的`j2`为$$j2(i)$$
```math
j2 = \max_{i = 1}^{n} j2(i)
```
那么如果$$m < j2$$，答案是$$j2 \cdot (m+1)$$
否则答案如前所述是$$j2\cdot j2 + (m+j2)\cdot (m-j2+1) / 2$$

### 强化版本
**[D2. Turtle and a MEX Problem (Hard Version)](https://codeforces.com/contest/2003/problem/D2)**
问题和前面的类似，不过这里要求每一个$$i$$**只能被选择一次**
注意，这个问题中，数和数之间是相互独立的
比如说你考虑计算`f(5)`，你选择了序列`i`，得到一个最大的 mex
接着考虑计算`f(8)`的时候，你仍然可以选择序列`i`，得到最大的 mex

**算法分析**

> 只考虑一个序列的情况是怎么样的？

注意到$$x < j1$$，那么一次操作可以变成$$j1$$
$$x = j1$$，那么可以变成$$j2$$
$$x > j1$$，那么$$x$$不需要变

> 现在考虑每个`j1`可能变成`j2`，问题转化为，最远能够到达哪里？

对所有的$$i$$，$$j1 \to j2$$连一条有向边，因为$$j1 < j2$$一定成立，只需要做一遍** DAG + 记忆化**
可以求出对于`mex = x`的点，$$x \to dp_x$$，表示$$x$$能到达的最远编号节点

> 接着考虑`x < j1`的情况，它能走到`j1`，还能继续往前走吗？走到`dp(j1)`

不难发现，`x`要想走到`dp(j1)`，必然是存在两个不同的`i`，这两个不同的`i`的第一个`mex`值都是`j1`
换句话说，如果 DAG 中一个点的 `deg(j1) >= 2`，那么意味着`x < j1`的点，都可以走到`dp(j1)`

实际上，记第一个`mex`值为`mex1`，第二个`mex`值为`mex2`
我们会发现所有的`f`值都至少会$$\geqslant \max_i \text{mex1}(i)$$
经过上面的分析，记$$\text{mex1} = \max_i \text{mex1}(i)$$，这可以在$$O(\sum l)$$的复杂度求出
对于`deg[j1] >= 2`的点`j1`，更新`mex1 = max(mex1, dp[j1])`
这样，对于$$< j1$$的所有点，能够到达的最远距离都$$\geqslant \text{mex1}$$

> 再来分析`x > j1`的情况，可能还得具体考虑`[j1+1, j2-1], [j2], [j2+1, m]`这几段

那么首先考虑`[j1+1, j2-1]`的情况，实际上和前面大同小异
先看一看`deg(j1)`，如果`deg(j1) >= 2`，那么最远可以走到`dp(j1)`
否则，这些点不做任何修改就是最优的
可以考虑在** DAG + 记忆化 dp**之后，对那些**走不出去**的点（即`dp(x) = 0`）的点
置为`dp(x) = x`，这样这种情况就可以求解了，
`x in [j1+1, j2-1]`走的最远的点是`max(mex1, dp(x))`

对于`x >= j2`的情况，记$$\text{mex2} = \max_i\text{mex2}(i)$$
所有的值不论怎么变，都无法超过$$\text{mex2}$$
对于`[mex2, m]`的值，不做任何修改才是最优的，这部分用等差数列求和直接计算即可
剩下的`[j1+1, mex2]`的情况，经过任意一次操作，和之前分析的一样
要么沿着 DAG 的边从`j1`走到`dp(j1)`
要么就是不做改变，对于没有出度的点，我们记`dp`值是他们本身`dp(x) = x`，也是走到`dp(x)`
要门就是沿着某一个`deg >= 2`的`j1`走到`mex1`去

综上所述，`x in [j1+1, mex2]`的答案是`max(mex1, dp(x))`
`x in [mex2+1, m]`的答案是这部分的等差数列的求和

## Codeforces Round 948 (Div. 2)
**[C. Nikita and LCM](https://codeforces.com/problemset/problem/1977/C)**
**问题描述**
给定一个长度为$$n$$的数组$$a$$，如果$$a$$的一个子数组$$b$$，满足$$b$$的`LCM`不在$$a$$中
那么就认为$$b$$是特殊的，求解$$a$$中特殊子数组中，最长的长度

### 算法分析
一开始想法是用 dp 来做，后来发现 dp 不太能做
$$dp(i, j)$$考虑子序列从$$i$$开始，到$$j$$能够得到的最大长度
考虑$$a_j$$这个位置能不能选，然后去转移，但会出现一个问题，比如有一组数
`2 3 ..... 6 ....  10000`，这个时候`dp`到`3`的时候，我们发现`lcm(2, 3) = 6`，`6`出现过了
`3`这个位置不能选，但其实你选进来也无妨，因为后面会有一个很大的数`10000`
这样`lcm(2, 3, 6, 10000) > max`，肯定不会在$$a$$中出现，dp 不太好转移

那么观察性质
首先，如果`lcm(a1....an) > max`一整段都比`max(a)`来的大，那么很显然一整段都可以选进来
或者我们可以暴力先判能不能一整段都选，一整段记为`lcm(all)`

否则的话，就说明有一些数是不能够被选进来的，那么最后的`lcm`一定是`lcm(all)`的**因子**
可以暴力枚举这个因子，复杂度是$$O(\sqrt{n})$$的
对枚举的每个因子$$x$$，遍历`a`，如果$$a_i \mid x$$，那么`a[i]`就可以被选进来，`len += 1`
用一个`val`统计答案`val = lcm(val, a[i])`，当`val == x`的时候，`ans = max(ans, len)`

## Educational Codeforces Round 118
**[Educational Codeforces Round 118 D. MEX Sequences](https://codeforces.com/contest/1613/problem/D)**
**问题描述**
定义一个序列是`mex-correct`的，当且仅当对每一个$$i \in [1\cdots k]$$都有
$$|x_i - mex(x_1, x_2, \cdots, x_i)| \leqslant 1$$（前缀 mex）
现在要你统计一个序列$$a$$不同的`mex-correct`子序列个数
如果子序列相同，但是**下标**是不同的，那么会被认为是不同的子序列

### 算法分析
![](/media/content_img/edu118D.png)
如上图所示，要想前缀 mex 满足条件，前缀中数的值域必须如上图所示
**要么值域全覆盖`[0...?]`的一段区间，要么是值域距离最右端一个单位处有空缺**
不难想到用 dp 来统计答案，问题是，dp 的状态如何设计

$$dp_i$$，表示我们要考虑$$i$$这个位置，因为`mex`的值和`a[i]`之间，要有一些限制
`a[i]`要和**值域中，空缺位置的具体值**去比较，所以值域也要设计到状态维度中去
$$dp(i, j)$$ 表示考虑$$i$$这个位置，`mex`（也就是空缺位置）值是$$j$$时候的方案数
然后考虑状态转移，初步看来，这个算法好像是$$O(n^2)$$的

第一种的方案数，记为$$dp1(i, j)$$，第二种记为$$dp2(i, j)$$，考虑$$i \to i+1$$，令$$x = x_i$$
对于$$dp1(i, j)$$，我们有如下情况
如果$$x = j-1$$，那么$$dp1(i, j) \to dp1(i+1, j)$$
如果$$x = j$$，这种情况不合法，因为$$j \to j+2$$，`mex`值变化了`2`
如果$$x = j+1$$，那么$$dp1(i, j) \to dp1(i+1, j)$$

对于$$dp2(i, j)$$，我们有
如果$$x = j-1$$，那么$$dp2(i, j) \to dp2(i+1, j)$$
如果$$x = j$$，那么$$dp2(i, j) \to dp2(i+1, j+1)$$
如果$$x = j+1$$，那么$$dp2(i, j) \to dp1(i+1, j)$$

接下来考虑优化，注意到`mex`的值`j`与`a[i]`是高度相关的，$$j = a_i \pm 1$$
并且分析一下，不难发现，`mex`值随着前缀增加，是单调递增的
或者停在某个位置，然后隔一个单位，又递增，所以第二维$$j$$不需要遍历所有的$$1 \to n$$
而是只需要根据$$x \leftarrow a_i$$，维护前缀`mex`来转移
根据$$j = x \pm 1$$来讨论转移

```bash
int main() {
    vector<mint> dp1(n+2, 0), last1(n+2, 0);
    vector<mint> dp2(n+2, 0), last2(n+2, 0);
    dp2[0] = 1;

for (int i = 0; i < n; i++) {
        auto x = a[i];

for (int y = x-1; y <= x+1; y++) if (y >= 0) {
            last1[y] = dp1[y], last2[y] = dp2[y];
        }

dp2[x+1] += last2[x+1];
        dp2[x+1] += last2[x];
        if (x >= 1) dp1[x-1] += last2[x-1];

dp1[x+1] += last1[x+1];
        if (x >= 1) dp1[x-1] += last1[x-1];
    }

mint ans = 0;
    for (auto x : dp1) ans += x;
    for (auto x : dp2) ans += x;
    ans -= 1;

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

## Codeforces Round 947 (Div. 1 + Div. 2)
**[Codeforces Round 947 (Div. 1 + Div. 2) D. Paint the Tree](https://codeforces.com/problemset/problem/1975/D)**
**问题描述**
有一个$$n$$个点的树，一开始树的所有颜色都是白色
有两个棋子`A, B`，`A`可以把白色节点染成红色，`B`可以把红色节点染成蓝色
一开始两个棋子分别在`a, b`两个点，如果`a = b`，那么`a`这个节点颜色是蓝色
否则的话，`a`这个节点就依然是红色

每一次移动，都需要做两件事情，第一件是把`a`移动到相邻的位置上
第二件是把`b`移动到相邻位置上，颜色相应要变化

问把树染成蓝色需要的最小代价
### 算法分析
先考虑简单情况，$$a=b$$，答案很显然就是$$n-1$$
如果$$a \neq b$$，大概能想到一种策略是`a, b`**相遇**，相遇之后再一起走
这样假设相遇前的点的个数是$$n_1$$，相遇后的点的个数是$$n_2$$，那么$$n_2$$只要走一遍
而$$n_1$$要走两遍（先染成红色，再染成蓝色），答案是$$2(n_1 - 1) + (n_2 -1)$$

那我们就考虑**相遇的点**，不放设他们在点$$u$$相遇，这样最优解就是
$$2 \cdot (n-1) - maxd$$，其中$$maxd$$，就是要让他们在$$u$$之后，**走尽量长的路**
换句话说，$$maxd_u$$可以认为是树上距离$$u$$最远的点

问题就是他们在哪里相遇，以及距离最远的点到底是哪个？
首先，距离最远的点，就是`dfs`后**深度最深**的点，这可以对深度`d[...]`求`max`

那么`a, b`相遇这个问题如何处理？实际上**直接模拟**就可以了
`a`往下走，`b`往上走
```bash
for i = 1 to n:		i 表示当前 a 节点的深度，往下走，深度不断增加
	if dep[b] == i:		break;
	
	if (dep[b] - 1 > i):	未相遇，b = pa[b], step++;
	else:	说明差一条边相遇，这个时候要继续走一步，b 称为 a 的父亲
	          b = pa[b], step++;
			  break
```

这样他们**相遇**的点就可以认为是，上述调整到相应深度的`b`节点，调整深度的额外代价是$$step$$
再执行`dfs(b)`，对深度`d[...]`求`max`，得到最远距离`mx`
答案就是$$2(n-1) - mx + step$$

## Educational Codeforces Round 165
**[Educational Codeforces Round 165 (Rated for Div. 2) C. Minimizing the Sum](https://codeforces.com/problemset/problem/1969/C)**
**问题描述**
给你一个数组，一次操作，你可以将一个元素改成任意的，与它相邻的元素
最多操作$$k$$次，问序列修改后最小的和是多少？

### 算法分析
这是一个很明显的 dp，$$dp(i, k)$$表示在$$i$$这个位置，改了$$k$$次的，得到的最小和
那么转移并不难写
如果$$a(i) \leqslant \min(a(i+1), a(i-1))$$，那么不需要改，$$dp(i, k) + a_i \to dp(i+1, k)$$
否则就改成最小值，$$dp(i, k) + \min \to dp(i+1, k+1)$$

但是这样做会存在一个问题，如果最优策略中，我们把$$a(i)$$改成$$a(i-1)$$，那么之后怎么决策？
之后有可能出现的情况是，比如$$a(i+l)$$特别小，这样提前把$$a(i)$$改成$$a(i-1)$$就亏了
应该把$$a(i+l) \to a(i)$$都改成$$a(i+l)$$

那我们观察性质，不难发现，要改，就是会把一个**连续的段**，都改成最小值
因为$$k$$很小，我们可以暴力枚举这个连续的段，这样$$O(k^2)$$的代价暴力
假设说从$$i$$开始，我们花了$$l$$次修改，那么影响的区间是$$[i, i+l]$$
转移到$$dp(i+l+1, k+l)$$

那么转移方程如下
$$dp(i, k) + \min[i, i+l] \cdot (l+1) \to dp(i+l+1, k+l)$$

## Codeforces Round 960 (Div. 2)
**[Codeforces Round 960 (Div. 2) D. Grid Puzzle](https://codeforces.com/problemset/problem/1990/D)**
**问题描述**
给定一个数组`a[1...n]`，你有一个`n * n`的方格，对于第$$i$$行，只有前面$$a_i$$个方格是黑色的
其他都是白色
你可以执行以下操作，任意次，按任意顺序
第一是将$$2 \times 2$$的子方格染成白色
第二是将一整行都染成白色

问把所有的方格都染成白色的最小操作次数

### 算法分析

> 什么时候只会用到方格染色？

注意到，如果$$a\_i \leqslant 2$$并且$$a\_{i+1} \leqslant a\_{i}$$，通过对$$i$$的一次方格染色
就可以免去$$i+1$$的染色操作

而用行染色，将第$$i, i+1$$均变成白色，需要$$2$$次的操作代价
考虑什么情况下，可以用$$2$$次的方格染色，来代替行染色？
![](/media/content_img/CF960D.png)

> 怎么贪心？

不难发现，在某些情况下，我们可以通过方格染色，来让下一行也染色一部分
从而减小下一行染色的代价
但如果$$a_i > 4$$，直接染这一行是最优的
只需要考虑$$a_i \leqslant 4$$，然后贪心地对每一行用方格染色
同时要判断这一行**会不会受上一行染色的影响**，如果已经被影响到了，这一行其实不需要额外染色的代价

具体的贪心过程，需要对`tag1 = 0 or 1,   tag2 = 0 or 1`**分类讨论**

如果`tag1 = 0, tag2 = 0`，那么考虑`a[i]`
若`a[i] = 0`，不需要进行任何操作
若`a[i] <= 2`，不论如何都需要一次操作`res += 1`，`tag1 = 1`
不考虑`2 < a[i] <= 4`的情况，根据上面的讨论，这种情况采用方格染色，那一定是
**前一半被染了，后一半还没染**的情况

如果`tag1 = 1`，首先要令`tag1 = 0`，此时不需要染前半部分了
考虑`a[i] <= 2`，都不需要操作
否则，一定会操作一次`res += 1`
当`a[i] <= 4`的时候，会采用方格染色，染后半部分，`tag2 = 1`

如果`tag2 = 1`，那么令`tag2 = 0`，因为后半部分不需要染色了
但是前半部分，可能有**残留，未染完的**，判断需不需要额外染色
如果`a[i] = 0`，不需要额外染色
否则都至少需要一次染色操作，`res += 1`
如果`a[i] <= 4`，那么会采用方格染色策略，此时只需要染前半部分`tag1 = 1`
否则采用行染色策略

上一篇：图的dp 下一篇：codeforces上的dp题（二）

看完文章有啥想法