codeforces上的dp题（二）

[[ slider_text ]]

[[ item.c ]]

codeforces上的dp题（二）

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

dp dp计数 结论推导

## Codeforces Round 911 (Div. 2) C
**[Codeforces Round 911 (Div. 2) C. Anji's Binary Tree](https://codeforces.com/problemset/problem/1900/C)**
**问题描述**
给定一个二叉树，根节点是`1`，你从根节点开始移动，根据一个序列移动
当一个节点上的数是`U`，往上移动，`L`往左儿子，`R`往右儿子，不存在的话就不移动

现在给你一个移动序列，你要想从根节点移动到叶子结点（移动到哪个叶子结点无所谓）
如果能顺利到达叶子结点，那么无需修改移动序列
否则你要额外操作，每一次额外操作，需要选移动序列上的字符，把它改成`L or R`
现在需要你最小化修改操作的次数

### 算法分析
一开始的想法是用点带权
```bash
if u 不是 leaf 节点，并且 u 无法向下走：		cost(u) = 1
else:	cost(u) = 0
```
然后考虑树形 dp，$$dp_u = \min(dp[l_u], dp[r_u]) + cost(u)$$

> 但后来发现这种情况有问题

![](/media/content_img/CF911C.png)

这种情况把点带权稍微改一下就可以了，**这个问题中一个节点只有一个父亲**
所以`cost(u)`定义成从父亲`pa(u)`进入这个点`u`的**额外代价**，其中根节点的`cost`是`0`
```bash
对于左儿子边(u, le(u)), 右儿子边(u, ri(u))
如果 str[u] = 'L'，那么 cost( le(u) ) = 0，否则进入 le(u) 需要有 1 的代价
```
这同样可以用**树形 dp + 记忆化**求解

## Codeforces Round 911 (Div. 2) D
**[Codeforces Round 911 (Div. 2) D. Small GCD](https://codeforces.com/problemset/problem/1900/D)**
**问题描述**
定义$$f(a, b, c)$$，排序$$a \leqslant b \leqslant c$$，返回$$\text{gcd}(a, b)$$
忽略$$c$$，给你一个数组`a`，然后你要计算不同的下标三元组$$1\leqslant i < j < k \leqslant n$$
```math
\displaystyle
\sum_{i = 1}^{n}\sum_{j = i+1}^{n}\sum_{k = j+1}^{n} f(a_i, a_j, a_k)
```

### 算法分析
首先这是一个三元组问题，一般的思路都是枚举$$j$$，然后看看$$a_i$$有多少种选择，
$$a_k$$有多少种选择，然后乘起来统计到答案中

> 假设我们已经知道$$\text{gcd}(a_i, a_j) = g$$，那么答案是什么呢？

对$$a$$排序之后，只需要关注下标，根据问题描述$$[j+1, n]$$这些数对答案没有影响
`ans += g * (n - j)`

> 现在的问题是$$g$$怎么处理

注意到题目的数据范围，而$$g$$一定是某个$$a_j$$的因子，枚举$$a_j$$，同时枚举因子
可以在$$O(n \sqrt{n})$$复杂度内处理完成，题目给的值域范围也不是很大，因子总个数也不会太多
这样大致可以想到以下算法

枚举$$g$$，$$a_i, a_j$$都是$$g$$的倍数，同时枚举倍数
那么$$a_i = g\cdot m_1, a_j = g\cdot m_2$$，同时要求$$(m_1, m_2) = 1$$且$$m_1 \leqslant m_2$$
对每个$$g$$，枚举它的倍数，并统计符合条件的$$m_1, m_2$$有多少个
假设为$$f_g$$个，那么答案就是`ans += g * f(g) * (n - j)`

这样看起来好像可行的，排序后，先枚举$$j$$，得到$$a_j$$
然后枚举$$a_j$$的每一个因子$$g$$，同时也可以求出$$m_2$$
然后再枚举$$\leqslant m_2$$，并且$$(m_1, m_2) = 1$$的$$m_1$$
看一下前面出现过的$$a_i = g\cdot m_1$$有多少个，这个可以前缀维护，记为`cnt[ g*m1 ]`
那么答案就是枚举`j`，枚举因子`g`，`m2 = a[j] / g`，再挨个考虑$$(m_1, m_2) = 1$$的`m1`
`ans += cnt[ g*m1 ] * (n - j) * g`

> 但是这样的做法有一个问题，枚举$$(m_2, m_1) = 1$$的$$m_1$$并不容易

但是**枚举一个数的因子，或者倍数**是容易的
对于枚举的每个`a[j]`，以`a[j]`的一个因子`g`作为`gcd`的`i`有多少个呢？

不难想到可以维护，对于因子`x`，`cnt(x)`表示含有因子`x`的数的个数
因子`x`能否作为 gcd 呢？不一定，但可以容斥一下
**g = gcd 一定是`a[j]`的因子，但是还需要扣除`g 的倍数作为gcd`的那部分**
`(含有因子 x 的数的个数) - (含有 x 的倍数作为 gcd 的数的个数)`，这好像就解决了

具体来说，**维护前缀**，`cnt(x)`表示含有`x`作为因子的数的个数
`g(x)`表示**前缀中**，`x`能和`a[j]`构成`gcd`的数的个数

统计的时候，先令`g(x) = cnt(x)`，然后枚举`x`的倍数，这里不需要枚举所有的倍数
只需要看看`m2 = a[j] / x`，考虑枚举`m2`的因子，`g(x) = g(x) - g(x * m2的因子)`
`x`的倍数，只看不超过`a[j]`的那一部分
同时统计答案`ans += g(x) * (n - j) * x`

然后我们考虑把`a[j]`加入集合中，对其所有因子维护`cnt(x) += 1`

> 特别注意，这里`g(x) = g(x) - g(x * m2 的因子)`

要保证计算`g(x)`的时候，`g(x * m2 的因子已经被算出来了)`
所以**枚举因子的时候要从大到小枚举**

## Codeforces Round 911 (Div. 2) E
**[Codeforces Round 911 (Div. 2) E. Transitive Graph](https://codeforces.com/problemset/problem/1900/E)**
**问题描述**
给定一个$$n$$个点$$m$$条边的有向图$$G$$，一开始图$$H$$和$$G$$相同
要在$$H$$上面做若干次操作
如果$$H$$中存在三个点$$a, b, c$$，如果有边$$(a, b), (b, c)$$，但是$$(a, c)$$没有边
添加一条边$$(a, c)$$
重复上面步骤直到不存在这样的三元组

同时$$H$$上的点有权值$$a_u$$
考虑一条长度为$$k$$的简单路径，路径的权值记为$$\sum a(v_i)$$
在所有简单路径中，找到一条最长的，并且最小化最长简单路径的权值

### 算法分析
这是一个关于**有向图可达性问题**，可以考虑 SCC
最长简单路径，实际上就是在**可达的点中，选取尽量多的点**

> 先考虑 SCC 中的点，加边后有什么影响？

发现 SCC 中的点，加边操作是没有影响的，因为计算路径权值是**点权而非边权**
而最长简单路径中，SCC 的点都要选进来
题中的操作只是把 SCC 变成完全图而已，不影响最长路径的权值

> 自然想到缩点，考虑缩点后的 DAG

假设说有一条路径$$SCC_1 \to SCC_2$$
在原图中，经过的点记为$$v_1 \to v_2 \to v_3$$，加边之后呢？
新加的边那么是$$v_1 \to v_3$$，**沿这条新加的边走是不划算的**，因为跳过了某些点
无法做到经过的点最多

> 综上所述

所以，只需要在原图$$G$$中缩点，跑一遍 DAG dp 即可
缩点后`u`的儿子是`{v1, v2, ..., vi, ..., vm}`，`dp1(u)`表示`u`出发到终点经过的最大点数
`dp2(u)`表示沿着最大点数路径走，能够得到的最小权值和，首先
$$(\max_i dp1(v_i)) + sz(u) \to dp1(u)$$

之后考虑扫描所有儿子，如果$$dp1(v_i) + sz(u) = dp1(u)$$，那么接着转移
$$(\min_i dp2(v_i)) + cost(u) \to dp2(u)$$，根据 dag dp 可以求解

## 树形 dp 求树的直径
![](/media/content_img/DP-diameter.png)

扫描并维护$$u$$的每一个分支，$$dp(u)$$表示已扫描的分支中，从$$u$$**往下最长的**路径
假设当前考虑的儿子是$$v$$，先执行一遍`dfs(v)`，求出$$dp(v)$$
直径首先可以是$$res \leftarrow \max(res, dp(u) + e(u, v) + dp(v))$$

然后尝试把`v`和父亲`u`合并，更新$$dp(u) = \max(dp(v) + e(u, v))$$
```bash

auto dfs = [&](auto self, int u, int fa) -> void {
	for (auto [v, e] : G[u]) {
		if (v == fa) continue;
		self(self, v, u);

chmax(res, dp[u] + e + dp[v]);
		chmax(dp[u], dp[v] + e);
	}
};
```

## Educational Codeforces Round 158
**[Educational Codeforces Round 158 (Rated for Div. 2) D. Yet Another Monster Fight](https://codeforces.com/contest/1901/problem/D)**
**问题描述**
有$$n$$个怪物，每个怪物的 HP 为`a[1...n]`，现在有一个AOE
这个技能有一个初始伤害$$x$$，击中一个怪物，这个怪物是哪个可以选择
然后，技能会随机再攻击一个怪物（除了第一个被攻击的），每个怪物都只会被攻击一次
随机被攻击的怪物满足两个条件，它从没被击中过，但是它的邻居已经被击中
伤害会衰减，第一次攻击伤害是$$x$$，然后依次衰减成$$x-1, x-2, \cdots$$

现在我想用一次 AOE 就杀死所有怪物，要最小化这个初始伤害
闪电的 AOE 是随机的，即要考虑最坏的情况也可以杀死怪物

### 算法分析
**注意**，伤害衰减只和距离有关，和怪物的血量无关，原来伤害是$$x$$，消灭了$$a_i$$
伤害会变成$$x - 1$$而不是$$x - a_i$$
![](/media/content_img/EDU158D.png)
很明显这个问题是可以二分的，现在问题转化为

> 给你一个初始伤害$$x$$，问能不能杀死所有怪物

注意，这里的怪物一旦被消除，是会直接消失的，原来不相邻的，可能会变相邻
消去一整个区间的伤害衰减，实际上是`len - 1`，其中`len`为区间长度
假设消去区间第一个数用的伤害是$$x$$，那么消去区间最后一个数，伤害衰减为$$x - (len - 1)$$

要想消去$$a_i$$，$$x$$一定会打在包含$$i$$的某一个区间，并且伤害衰减完之后，依然$$\geqslant a_i$$

> 考虑消除$$a_j$$，对每个$$a_j$$都是单独考虑的

要想消除$$a_j$$，最坏情况就是，$$x$$一开始打在某个位置$$i$$，**经过最大的伤害衰减**
其他都打完了，最后才打$$j$$，于是我们讨论最大伤害衰减

如果$$i = j$$，没有伤害衰减，但是$$x < a_i$$一定不行
如果$$i \in [1\sim j-1]$$，最大伤害衰减一定是把$$1 \sim j-1$$这些位置全部都打完，然后再打$$j$$
因为$$j \sim n$$的这些位置并没有被打过，所以不可能出现先打$$j$$右边的，再打$$j$$的情况
如果$$i \in [j+1 \sim n]$$情况，对称的，先把右边全部打完，然后再打$$j$$

综上所述，对每个$$j$$，取$$\max$$
令$$x = \max_j( a_j[j = i], (a_j+(j-1))[j\geqslant i+1], (a_j + (n-j))[j \leqslant i-1] )$$
因为要枚举初始位置$$i$$，咋一看复杂度好像是$$O(n^2)$$

> 换一个角度来想这个问题，考虑二分$$x$$，枚举$$x$$能够打败每一个$$a_j$$，要满足哪些限制？

**这个时候，可以从反方向来思考，判断什么情况下，不满足？从而得到某些限制**
$$x < a_j$$，肯定$$x$$不合法

如果$$x$$打在$$< j$$（左边）的位置上，当且仅当$$x \geqslant a_j + (j-1)$$时能够消除$$j$$
如果$$x < a_j + (j-1)$$，左边也不能打，只能打在$$j \sim n$$（右边）的位置
最左边能打的位置只能是$$ le = \max(le, j)$$

然后再看一下右边能不能打，能打成功（消除后缀），那么没问题
不能打成功，那么$$x$$不合法
如果$$x < a_j + (n - j)$$，那么右边不能打，只能打$$1 \sim j$$的位置，最右边只能打$$ri = \min(ri, j)$$

初始化$$le = 1, ri = n$$
每次扫描，看一下限制，$$le = \max(le, j), ri = \min(ri, j)$$，如果$$le \leqslant ri$$就合法
否则不合法，二分+扫描判断，复杂度$$O(n \log n)$$

> 实际上，根据第二点的分析，我们也可以写出如下$$O(n^2)$$的算法

```bash
枚举初始位置，for i，初始伤害不知道，设为 x
		枚举 j，考虑初始伤害，经过最大衰减，仍能够打掉每一个 j
		
		for j = [1...i-1]，只打 j 右边，经过最大的衰减是 (n - j)，x >= a[j] + (n - j)
		j = i，不需要衰减，x >= a[j]
		for j = [i+1...n]，只打 j 左边，经过最大的衰减是 (j - 1)，x >= a[j] + (j - 1)
```

如上算法可以考虑优化，枚举每一个$$i$$，**改变它的权值**
对于前缀，考虑前缀最大值，后缀考虑后缀最大值
这样$$pre_j = a_j + (n - j), suf_j = a_j + (j-1)$$
预处理一个前缀最大值和后缀最大值，求出来之后，枚举初始位置$$a_i$$
$$res = \max(a_i, pre(i-1), suf(i+1)), ans = \min(ans, res)$$即可

## Codeforces Round 932 (Div. 2)
**[Codeforces Round 932 (Div. 2) C. Messenger in MAC](https://codeforces.com/contest/1935/problem/C)**
**问题描述**
给定$$n$$条信息，选$$k$$条，每条信息的阅读时间为
```math
\displaystyle
tot = \sum_{i = 1}^{k} a(p_i) + \sum_{i = 1}^{k-1} |b(p_i) - b(p_{i+1})|
```
只读一条信息的代价是$$a(p_1)$$，不读信息的代价是$$0$$
现在读信息的总时间给定，是$$L$$，你要选一些信息来读，问最多能读多少条信息
使得读完这些信息的总时间$$\leqslant L$$

### 算法分析
不难发现，能够选的信息条数记为`sz`，具有单调性，所以考虑二分
问题转化为，你要从这些信息中选择`sz`条，看看满不满足$$\min tot \leqslant L$$

> 注意 tot 的表达式

不难发现，$$\sum |b(p\_i) - b(p\_{i+1})|$$仅仅与$$b$$的最大值和最小值有关
不妨记为$$bmin, bmax$$，这部分的和最小值是$$bmax - bmin$$

如果按$$b$$值来排序，相当于说，**起点和终点**都会在一定范围内
容易想到**枚举起点**$$i$$，那么终点$$j \geqslant i+sz-1$$，至少要在`i+sz-1`处

还有很重要的一点是，$$i, j$$是一定要选的，至于$$[i+1, j-1]$$中间的数
只需要考虑他们的$$a$$的值，与$$b$$的值无关

> 那对于$$k \in [j+1, n]$$的数呢？如果选择这部分，因为我们是按$$b$$大小排序的
$$b_k - b_i$$一定会越来越大，但要考虑的一种情况是，如果**这部分的$$a$$特别小**
那么就可以选择偏后位置的$$a$$

所以我们考虑用**大根堆**维护
首先，枚举$$i, \quad j = i+sz-1$$
暴力把$$[i+1, j-1]$$中的$$sz - 2$$个元素全部插入大根堆中，这部分元素我们只关系它的$$a$$值
顺便统计一下他们的和$$sum$$
```math
res \leftarrow sum + (a_i+a_j+|b_j - b_i|)
```

接着考虑$$k \in [j+1, n]$$，这部分**维护**
此时$$k$$作为新的终点，那么$$k-1$$这个位置，能不能加入大根堆中？
```bash
let j2 = k-1
if a[j2] < heap.top:
		大根堆弹出最大元素，j2 进堆，维护 sum
		sum -= heap.top,  sum += a[j2]
		heap.pop,  heap.push(a[j2])
```
然后同样更新$$res$$，$$res \leftarrow sum + (a_i + a_k + |b_k - b_i|)$$
$$res \leqslant L$$就是合法的$$sz$$

## Codeforces Round 936 (Div. 2)
**[Codeforces Round 936 (Div. 2) C. Tree Cutting](https://codeforces.com/contest/1946/problem/C)**
**问题描述**
给你$$n$$个节点的一棵树，然后你要删掉$$k$$条边，使得剩下的每个连通块的大小都$$\geqslant x$$
然后你要最大化这个$$x$$

### 算法分析
这是一个最小值最大的问题，可以考虑**二分答案**
那么问题变成了，给你一个$$x$$，在树上删除$$k$$条边，能不能使得每个连通块大小都$$\geqslant x$$

算法也不难写
```bash
用 num 统计当前已经断开的边的数量，x 表示二分的答案
dfs(u, num):
	sz[u] = 1;
	for v : G[u]:
		dfs(v, num)
		
		如果子树能断开，就贪心地立即断开
		否则跟父亲合并
		if (sz[v] >= x and num < k) num += 1
		else sz[u] += sz[v]
		
然后看一下是否满足 num >= k and sz[1] >= x
如果满足，那么 x 就合法，否则 x 就不合法
```

## Educational Codeforces Round 164
**[Educational Codeforces Round 164 D. Colored Balls](https://codeforces.com/contest/1954/problem/D)**
**问题描述**
有$$n$$种不同颜色的球，第$$i$$种颜色的球有$$a_i$$个
分组限制：
这些球分成若干组，每一组最多有$$2$$个球，并且颜色要互不相同（不能同一种颜色的`2`个球分一组）

那么$$n$$种颜色，可以构成$$2^n$$种不同的集合（每个颜色，都有放/不放`2`种选择）
定义集合的权值如下：
集合满足以上分组限制，能够得到的最小分组数量
比如有`3`种颜色，每种颜色的球数量分别是`{3, 1, 7}`，那么`{3, 1, 7}`这个集合
它的权值是`7`，因为按照分组限制，最小的分组数量就是`7`组
（`7`个颜色相同的球，必须拆开，位于不同的组里）

计算这$$2^n$$个子集的权值之和

### 算法分析一
![](/media/content_img/EDU164D1.png)
问题可以转化成，有两组球，一组球的个数是$$len$$，对这组中的每一个球
尝试在另一组中找一个跟他**配对**，最后使得配对的数量尽可能多
![](/media/content_img/EDU164D2.png)

一般来说，这个题目是怎么求解的？用 dp 表示**方案数**
`ans += dp(当前状态) * (当前状态集合的最小权值)`，权值在这个问题中，可以认为如上图所示的长度
根据上面的分析，长度似乎和**集合中总元素个数**$$s$$有关
根据题目中给的条件$$\sum a \leqslant 5000$$，可以猜想状态设计成$$dp(i, s)$$
表示正在考虑$$i$$这个点，集合的元素个数是$$s$$，此时对应的方案数，尝试分析一下

如果$$a_i > s$$，根据题中描述，相同的元素不能放一组，那么很显然，长度变成了$$a_i$$

考虑$$a_i \leqslant s$$，此时，不论怎么样，$$a_i$$**都能全部完成配对**
那么分为两种情况
第一种，就是原来集合中的数，已经配对了，配对长度是$$len$$，并且$$len = \lceil s/2\rceil$$
那么根据上面的分析，将$$a_i$$加入集合中，$$len$$要拿出一部分去和$$a_i$$配对
$$len$$剩下的长度为$$len - \lceil a_i / 2 \rceil$$，再加上新的$$a_i$$的长度

答案是$$len + \lceil a_i / 2 \rceil = \lceil \dfrac{2len + a_i}{2} \rceil = \lceil \dfrac{s+a_i}{2} \rceil$$

第二种情况，就是原来集合中的数并没有完全配对，新加入一个$$a_i$$之后会怎么样？
可以考虑将$$a$$从小到大排序
$$a_i$$加入集合中，可能有未配对的元素，那么未配对的元素一定不是$$a_i$$（因为$$a_i$$一定有配对）
那么可不可能是原先集合中的元素？假设为$$b$$，$$\sum b = s$$
如果是原先集合中的元素，那么$$b$$拿出一部分使得$$a_i$$全部配对，还剩下未配对的一部分
这就意味着$$\sum b > a_i$$，记$$\Delta b = \sum b - a$$

注意到，这时候的**最优策略**，应该是令$$\Delta b$$（孤立的段）和$$a$$先去配对
剩下的元素由于已经是配对的了，直接接在之后，如果还有没配对的，按照上述分析，
采用**交替放置**策略，也能完成配对
剩下的元素和不妨记为$$s'$$，那么剩下部分对长度的贡献一定是$$\lceil \dfrac{s'}{2} \rceil$$
接下来分类讨论$$\Delta b = s-a$$和$$a$$的配对情况

第一种情况，$$s-a \leqslant a$$，这时候能够把多出来的孤立段$$\Delta b$$和$$a$$匹配
其余的元素，可以按照**交替放置**的策略，进行完全匹配
此时的集合长度是$$\lceil \dfrac{s + a_i}{2} \rceil$$

第二种情况，我们有$$s - a > a, \quad s > 2a$$
不妨假设原先集合中有两种元素，其数量分别是$$b, c$$，也就是说
$$b+c > 2a$$，但是，我们**如果从小到大排序**，然后依次将元素放入集合中
就一定有$$c < b < a$$，也就是说$$(b - a) + (c - a) < 0$$，这与$$b+c > 2a$$**矛盾**

> 综上所述，从小到大排序后，依次放入集合，集合的长度变成$$\lceil \dfrac{s+a_i}{2} \rceil$$

### 算法分析二
记$$dp(i, j)$$表示当前正在考虑第$$i$$个元素，已经选择的总个数（总长度）是$$j$$
此时的方案数，考虑答案怎么统计

假设加入第$$i$$个元素后，总长度变成了$$L$$，那么$$ans += |L| \cdot dp(i, j)$$
其中$$j$$表示已经选了这么多元素，因为 dp 过程$$j$$是单调递增的
所以每个不同的$$j$$，都贡献了$$|L|$$的长度，贡献了几个$$|L|$$的长度呢？
已知$$i$$这个位置是一定要选的，因为它决定了$$|L|$$的大小，剩下的位置没有限制
所以方案数为$$dp(i, j)$$（表示已经考虑了$$1\cdots i-1$$的前缀，正在考虑$$i$$）
然后转移$$dp(i, j) \to dp(i+1, j+a_i)$$

状态转移方程不难写
1）$$a_i$$一定要选进去，那么考虑
如果 $$a_i > j$$，$$dp(i, j)\to dp(i+1, j+a_i)$$，位置$$i$$的贡献是$$|a_i| \cdot dp(i, j)$$

如果 $$a_i \leqslant j$$，$$dp(i, j) \to dp(i+1, j+a_i)$$，位置$$i$$的贡献是$$\lceil\dfrac{j+a_i}{2}\rceil \cdot dp(i, j)$$

2）$$a_i$$不选，那么$$dp(i, j) \to dp(i+1, j)$$
用滚动数组优化

## Educational Codeforces Round 150
**[Educational Codeforces Round 150 C. Ranom Numbers](https://codeforces.com/problemset/problem/1841/C)**
**问题描述**
给你一些仅有`A, B, C, D, E`组成的字符串，`A = 1, B = 10, C = 100, D = 1000, E = 10000`
定义 Ranom numbe（即字符串权值） 值如下，它是字符串所有字符的权值和
但是某些字符应该算负数，当且仅当这个字符后面（后缀中），有比它大的字符
现在你有一个串，你可以改变**不超过一个位置**，然后你需要计算最大的字符串权值

### 算法分析
因为最多只修改一次，可以枚举，要修改成哪个字符，`for to = {A ... E}`
同时用`suf`来维护后缀最大值，从后往前 dp，怎么设计 dp 的状态呢？

$$dp(i, 0/1)$$表示考虑$$i$$这个位置，将要决策`str[i]`修改与否
同时后缀$$[i+1\cdots n]$$已经决策完成，`0`表示未修改，`1`表示修改过
然后`suf = max(suf, str[i])`或者`suf = max(suf, to)`

**但是这有一个问题**
就是`suf`未必都是原字符串的后缀最大值
有可能出现一种情况是，后缀中某一个位置$$j$$改成了`to`，但是接着扫描的过程中，
需要**反悔**，发现原先的位置不修改可能更优
这种存在**反悔**的情况，解决方法是把`suf`也设计到状态中去

$$dp(i, 0/1, suf)$$表示将要决策$$i$$这个位置，$$[i+1, n]$$已经决策完毕
后缀`[i+1...n]`中，`0/1`分别表示后缀是否发生修改，`suf`表示当前状态中后缀最大值

```bash
一开始令 dp(n, 0, A) = 0，其他 dp 值设计成 -inf

考虑 i 这个位置
for all suf = [0...5)，只转移 dp(i, 0/1, suf) != inf 的合法状态
不做修改：
	sgn = (str[i] < suf ? -1 : 1)
	dp(i, 0, suf) + sgn*str[i] --> dp(i-1, 0, max(suf, str[i]))
	dp(i, 1, suf) + sgn*str[i] --> dp(i-1, 1, max(suf, str[i]))
	
修改:
	sgn = (to < suf ? -1 : 1)
	dp(i, 0, suf) + sgn*to --> dp(i-1, 1, max(suf, to))
```
以上 dp 过程考虑**滚动数组**优化

## Educational Codeforces Round 157
**[Educational Codeforces Round 157 C. Torn Lucky Ticket](https://codeforces.com/problemset/problem/1895/C)**
**问题描述**
一个字符串是合法的，满足两个条件
第一是长度为偶数，第二是前一半的和等于后一半
现在给你$$n$$个字符串`s1, s2, ..., sn`，问有多少个二元组$$(i, j)$$
使得$$s_i + s_j$$合法，其中$$i = j$$也是可以的
注意，这里每个字符串的长度很小，不超过`5`

### 算法分析
题目不难，可以先预处理，然后对每个串，存下二元组`(len, sum)`
`mp[ {len, sum} ] += 1`表示满足串长为`len`，串的数字和为`sum`的串有多少个

然后遍历全部的串，发现$$s_i + s_j$$一半的和，要么是前缀，要么是后缀
枚举它等于$$\sum pre$$还是$$\sum suf$$
```bash
for l1 = 0 to len - 1:
	s2 = sum - s1, l2 = len - l1
	// half sum 和某个前缀相等
	dl = l1 - l2, ds = s1 - s2;
	res += mp[ {dl, ds} ]
	
	// half sum 和某个后缀相等
	dl = l2 - l1, ds = s2 - s1
	res += mp[ {dl, ds} ]
	
	s1 += str[l1];
```

## POI 2015 LOG 结论
这里再分析一些结论
**[POI2015 LOG](https://www.luogu.com.cn/problem/P3586)**
在自然数序列$$a_n$$上进行$$s$$次操作，每次选择其中$$c$$个非$$0$$数，将它们都减去$$1$$
记序列中$$\geqslant s$$的数的个数为$$cnt$$，$$< s$$的数和为$$sum$$
求证，序列能进行$$s$$次操作的充要条件是$$sum \geqslant s(c - cnt)$$

**充分性**

1）若$$c \leqslant cnt$$，那么一定可以（每次都选$$\geqslant s$$的数即可）
2）若$$c > cnt$$，那么首先这$$cnt$$个数（都$$\geqslant s$$）每一次肯定都会被选
每一次选的时候，要另外从$$< s$$的数中，补上$$c - cnt$$个，一次操作补$$1$$的代价
这样进行$$s$$次操作，一共需要补$$s(c-cnt)$$，就一定要有$$sum \geqslant s(c-cnt)$$

**必要性**

$$sum \geqslant s(c-cnt)$$时，能否一定进行$$s$$次操作
不考虑$$\geqslant s$$的$$cnt$$个数，只关心$$m = n - cnt$$个$$< s$$的数
每一次取$$d_0 = c-cnt$$个数减去$$1$$，那么问题转化成

给你$$m$$个元素的序列$$b_m$$，满足$$sum \geqslant s \cdot d_0$$
并且对于任意的元素，我们均有$$b_i < s$$，每一次操作都要求取出$$d$$个$$> 0$$的数减去$$1$$
证明，能够完成$$s$$次这样的操作，每次操作前，都有$$d$$个元素$$> 0$$

首先，一定是可以进行第一次操作的，我们考虑进行一次操作后，问题变成什么样
![](/media/content_img/POI2015.png)
1）如果没有残留，那么问题转化成，这些元素的和是$$sum_1 = sum_0 - d_0 = (s-1)\cdot d_0$$
令$$s_1 = s-1$$，现在问题变成了满足$$sum_1 \geqslant s_1\cdot d_0$$
对于任意元素，均有$$b_i < s_1$$，每次操作要取出$$d_0$$个数，这是原问题的一个子问题，递归解决

2）如果有残留，不妨设操作前有$$x$$个元素值为$$s-1$$，那么要处理$$y = x-d$$这部分
还记得我们一开始是怎么做的吗？
一开始我们忽略掉$$\geqslant s$$的$$cnt$$个元素，同样这里相当于$$s_1 \leftarrow s-1$$
我们也可以忽略掉$$\geqslant s_1$$的元素，也就是忽略掉$$y$$
因为这$$y$$个元素在后续的操作中，**一定会满足条件**，并且都会被选上
于是接下来的问题中，我们只需要考虑每次选择$$d_1 = d_0 -y$$个元素就可以了
这样，我们扣除残留元素，有
$$sum_1 ^{\prime} = sum_1 - y(s-1) \geqslant s_1\cdot d_0 - y \cdot s_1 = s_1 \cdot (d_0 -y)$$
$$sum_1 ^{\prime} \geqslant s_1 \cdot d_1$$

这样，原问题又转化成一个子问题
给你$$p\_{m-y}$$的序列，这些元素的和是$$sum_1^{\prime}$$，满足$$sum_1^{\prime} \geqslant s_1 \cdot d_1$$
这些数都$$p_i < s_1$$，你要每次选$$d_1 = d_0 - y$$个数减去$$1$$

递归求解子问题即可

上一篇：codeforces上的dp题（一）下一篇：codeforces上的dp题（三）

看完文章有啥想法