NOIP 冲刺之——dp

\(\texttt{0x00}\) 前言

本篇文章主要记录笔者 NOIP 冲刺阶段复习的各种 dp 题型及 tricks ans tips，同时也用于及时复习与巩固。

那么，开始吧。

\(\texttt{0x01}\) 线性 dp

线性 dp 对我来说是一类很捉摸不定的题型：她太综合了，可以和任何知识点合起来考，这里就先抛开“数据结构优化”的成分展开来讲。

线性 dp 的状态设计不一定都是一维的，是指在状态转移时在每一维上是线性转移。就比如：

\[dp_i = dp_{i – j} + c_i \]

这种式子就是线性 dp 的大概模样。

如果很幸运，你看出一道题有线性 dp 的做法，那么可以从几个方向入手：

1. 观察数据范围，这通常可以启发状态设计；
2. 注意题目中具有明显线性转移的语句；

然后根据设计出的状态，通常只需根据转移方程依次循环每个维度即可求解。

还需要抓住主要矛盾：找出 dp 的阶段，然后把它丢到最外层循环去。

接下来来看几道例题：

Frog 1

首先发现青蛙只能跳一格或两格，所以可以设 \(dp_i\) 表示青蛙跳到第 \(i\) 格所需的最小总费用。那么状态转移方程就是：

\[dp_i = \min\{dp_{i – 2} + \lvert h_{i – 2} – h_i\rvert, dp_{i – 1} + \lvert h_{i – 1} – h_i\rvert\} \]

Vacation

一共有 \(3\) 种活动，且不能两天做相同的活动，那么我们可以这么定义状态：\(dp_{i, 0/1/2}\) 表示到第 \(i\) 天且前一天做了什么活动（\(0\) 表示在海里游泳，\(1\) 表示在山上抓虫，\(2\) 表示在家做作业）能获得的最大幸福值。

状态转移方程：

\[dp_{i, 0} = \max\{dp_{i – 1, 1}, dp_{i – 1, 2} + a_i\} \]

\[dp_{i, 1} = \max\{dp_{i – 1, 0}, dp_{i – 1, 2} + b_i\} \]

\[dp_{i, 2} = \max\{dp_{i – 1, 0}, dp_{i – 1, 1} + c_i\} \]

答案就是第 \(n\) 天时三种活动活动中的最大值。

其实这道题也是状态机模型 dp 的一道经典题目。

Coins

表面上是概率 dp，但不要被唬住了，本质上还是一道简单的线性 dp。

通过题目描述（主要）和数据范围（次要）可以大概确定状态是二维的，\(dp_{i, j}\) 表示考虑前 \(i\) 个硬币，有 \(j\) 个正面朝上的概率。

对于第 \(i\) 个硬币，有概率朝上或朝下，那就都讨论一遍，得出状态转移方程为：

\[dp_{i, j} = dp_{i – 1, j – 1}\times p_i + dp_{i – 1, j}\times (1 – p_i) \]

顺便地，线性 dp 有一个优化空间的小技巧：滚动数组（其实在其它类型的 dp 中有时也会用到）。

比如这一题，我们发现每次只会用到 \(dp_{i – 1}\) 这一层里的东西，且最后求总和时也只用到 \(dp_n\) 这一层，那么假设现在我们开始求第 \(2\) 层的 dp 值了，她只会用到 \(dp_1\) 这一层的东西，\(dp_0\) 就可以扔掉了，这样就可以保证在 dp 的过程中始终只会占用两层的空间，换句话说，空间复杂度从 \(O(n^2)\) 优化到了 \(O(n)\)。

加滚动数组优化也很简单，这里我们只需要两层，那么就在所有第一维的地方加上一个 & 1，就行了。同理，如果需要 \(k\) 层，就加上 & k - 1。

综上，状态转移方程就变为了：

\[dp_{i \wedge 1, j} = dp_{i – 1\wedge 1, j – 1}\times p_i + dp_{i – 1\wedge 1, j}\times (1 – p_i) \]

Candies

挺有意思的一道题。

首先朴素 dp 很好想，根据数据范围大概可以猜出状态设计：\(dp_{i, j}\) 表示考虑前 \(i\) 个人，现在还剩下 \(j\) 个糖果的方案数。

那么状态转移方程为：

\[dp_{i, j} = \sum\limits_{k = 0}^{\min(a_i, m – j)}dp_{i – 1, j + k} \]

但是这样转移时间复杂度是 \(O(\sum a_iK)\)，考虑优化。

这里我想了一个十分类似完全背包优化的方法。

发现有很多重复项，所以可以列出相邻的项找关系。

把 \(dp_{i, j}\) 和 \(dp_{i, j – 1}\) 的表达式写出来：

dp[i][j]   =                dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][min(j+a[i]-1,m)] + dp[i-1][min(j+a[i],m)]

dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][min(j+a[i]-1,m)]

会发现他们中间有很多项都是完全一样的，所以 \(j\) 每次减一的时候就只用去掉一个尾巴，加上一个头就可以了。

for(int i = 1; i <= n; i++)
    for(int j = K; ~j; j--)
        if(j + a[i] < K) dp[i][j] = ((ll)mod + dp[i][j + 1] + dp[i - 1][j] - dp[i - 1][j + a[i] + 1]) % mod;
        else dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % mod;

P1541 [NOIP2010 提高组] 乌龟棋

根据数据范围题目描述不难猜到这个题是个多维度的线性 dp，直接来！

设已经使用了 \(a\) 张牌 \(1\)，\(b\) 张牌 \(2\)，\(c\) 张牌 \(3\)，\(d\) 张牌 \(4\) 所能获得的最大分数。

对于每一维都枚举一遍，设 \(v = a_{a + 2b + 3c + 4d}\)，那么状态转移方程为：

\[dp_{a, b, c, d} = \max(dp_{a, b, c, d}, dp_{a – 1, b, c, d} + v) \]

\[dp_{a, b, c, d} = \max(dp_{a, b, c, d}, dp_{a, b – 1, c, d} + v) \]

\[dp_{a, b, c, d} = \max(dp_{a, b, c, d}, dp_{a, b, c – 1, d} + v) \]

\[dp_{a, b, c, d} = \max(dp_{a, b, c, d}, dp_{a, b, c, d – 1} + v) \]

P11233 [CSP-S 2024] 染色

考场上犯糖了，不知道为什么跳了这道题，而且 20pts 的暴力也打挂了，可以说是一败涂地。

其实这道题还挺简单的，不管是暴力还是优化。

很显然的序列上线性 dp，先思考 \(O(n^2)\) 暴力。

设 \(dp_i\) 表示考虑前 \(i\) 位能获得的最大得分。

那么状态转移方程就为：\(dp_i = \max\limits_{1\le j < i}\{dp_j + val(j + 1, i)\}\)，\(val(i, j)\) 表示 \([i, j]\) 这段区间的贡献。

那么就可以 \(O(n^2)\) 预处理出所有的 \(val(i, j)\)，然后 \(O(n)\) 转移。

但是很快我们就认识到转移能优化成 \(O(1)\)，因为对于一个 \(i\)，选取她的左边第一个与她相同的位置转移一定是不劣的。

为什么呢？

因为 \(dp_i\) 的计算分为两步，第一步为 \(a_i\) 不产生贡献，即 \(dp_i = dp_{i – 1}\)，第二步为 \(a_i\) 产生贡献，那么只有左侧与其最靠近的同色的数 \(j\) 与 \(i\) 相同的才能对 \(dp_i\) 有贡献，这就限定了 \(a_j = a_i\)。

而且为了得到这个贡献也是不择手段——必须钦定区间 \([j + 1, i]\) 全为另一种颜色才行，也就是说，这一段区间里只有相邻且数值相同才能产生贡献，而且相邻且同色一定会被染成同色，这是因为将她俩染成同色不会影响其他任何东西。

令 \(pre_i\) 表示 \(a_i\) 左侧第一个等于 \(a_i\) 的位置，若 \(j\ne pre_i\) 的话，那么 \(val(j + 1, pre_i)\) 的非相邻的相同数的贡献就吃不到，而用 \(pre_i\) 转移的话就吃得到，而这种决策一定被 \(dp_{pre_i + 1}\) 包含，所以可以放心转移。

那么现在就可以将转移优化到 \(O(1)\)，但是预处理仍然是 \(O(n^2)\)，复杂度依然没有降下来。

注意到 \([j + 1, i]\) 这一段区间里只有相邻且数值相同才能产生贡献，所以不用开二维数组计算，直接一维前缀和即可。

综上所述，时间复杂度为 \(O(n)\)。

要特别注意！此时状态转移方程变成了：\(dp_i = \max\{dp_{i – 1}, dp_{pre_i + 1} + sum_{i – 1} – sum_{pre_i + 1} + a_i\}\)。

为什么是 \(dp_{pre_i + 1}\) 呢？因为若用 \(dp_{pre_i} + sum_{i – 1} – sum_{pre_i}\) 就没有统计到 \(pre_i + 1\) 的贡献，而这个贡献直接用前缀和数组是无法计算的（因为你无法知道 \(pre_i + 1\) 前面是否有一个数和她颜色数值都相同），但是 \(dp_{pre_i + 1}\) 就恰好包含了她而且是这种情况下的最优决策，所以应该用 \(dp_{pre_i + 1} + sum_{i – 1} – sum_{pre_i + 1}\) 来更新。

P1387 最大正方形

好像是一类比较有意思的题的最基础版本。

设 \(dp_{i, j}\) 表示以 \((i, j)\) 作为正方形的右下角时的最大边长。

那么可以看一下右下角的情况：

P1736 创意吃鱼法

\(\texttt{0x02}\) 区间 dp

对于这种 dp 我都是类比线段树的合并来理解，一般有很明显的区间性，通常采用枚举分界点的方式来转移。

\(\texttt{0x03}\) 树形 dp

和图论有明显的交集，可以借助图论的思想形象地思考问题和划分阶段，所以个人认为在某些方面比线性 dp 和区间 dp 好理解。

知识点 \(1\)：树上背包

知识点 \(2\)：换根 dp

题单

P3478 [POI2008] STA-Station

经典入坑题。

P2986 [USACO10MAR] Great Cow Gathering G

经典变式题。

P10974 Accumulation Degree

蓝书上的例题。

P11324 【MX-S7-T2】「SMOI-R2」Speaker

今天打的梦熊模拟赛的题，考场上忘了换根 dp 怎么写，所以只用 \(O(n^2)\) 骗了 52 pts……

其他：