Educational DP Contest Solution

cancan123456 · 2023-09-04 13:02:26 · 个人记录

为与国内 OI 传统保持一致，简化题意与原题中部分字母不同。

A Frog 1

题意：给定长 n 的序列 h_i，Frog 从 i 可以跳到 i+1 或 i+2，当 Frog 从 i 跳到 j 时你需要付出 |h_i-h_j| 的代价，求 1 到 n 的最小代价。

保证 1\le n\le10^5,1\le h_i\le10^4。

我们设 f_i 为从 1 到 i 的最小代价，那么有：

时间复杂度 O(n)，可以通过此题。

B Frog 2

题意：给定长 n 的序列 h_i，Frog 从 i 可以跳到 i+1\sim i+k，当 Frog 从 i 跳到 j 时你需要付出 |h_i-h_j| 的代价，求 1 到 n 的最小代价。

保证 1\le n\le10^5,1\le k\le100,1\le h_i\le10^4。

我们设 f_i 为从 1 到 i 的最小代价，那么有：

时间复杂度 O(nk)，可以通过此题。

C Vacation

题意：Taro 的假期有 n 天，第 i 天 Taro 可以选择三种活动，分别增长 a_i,b_i,c_i 高兴值，Taro 不能连续两天进行相同的活动。

保证 1\le n\le10^5,1\le a_i,b_i,c_i\le10^4。

我们设 f_{i,j} 表示已经考虑了 i 天，第 i 天选择第 j 种活动。

那么有：

时间复杂度 O(n)，可以通过此题。

D Knapsack 1 背包

题意：Taro 要从 n 个物品里选出若干个放进 Taro 的容量为 W 的背包里，每个背包有两个值 v_i,w_i，v_i 代表价值，w_i 代表体积，需要保证 \sum_{\text{选出}}w\le W，最大化 \sum_{\text{选出}}v_i 并输出。

保证 1\le n\le100,1\le W\le10^5,1\le w_i\le W,1\le v_i\le10^9。

我们设 f_{i,j} 为考虑前 i 个物品，\sum_{\text{选出}}w=j 的最大 \sum_{\text{选出}}v，那么有：

可以利用滚动数组将空间复杂度优化至 O(n)。

时间复杂度 O(nW)，可以通过此题。

E Knapsack 2 背包

题意：与上一题相同。

保证 1\le n\le100,1\le W\le10^9,1\le w_i\le W,1\le v_i\le10^3。

遇到这种 DP 状态非常多，但是 DP 值很小的时候，考虑交换 DP 状态与 DP 值，即，设 f_{i,j} 为考虑前 i 个物品，\sum_{\text{选出}}v=j 的最小 \sum_{\text{选出}}w，那么有：

答案是满足 f_{n,i}\le\sum v_i 的最大 i。

时间复杂度 O(n\sum v_i)，可以通过此题。

这个技巧用的比较少，我只见过 P1156 垃圾陷阱 可以这么做。

F LCS

题意：给定字符串 s 和 t，找到 s 与 t 的最长公共子序列，并输出。

保证 1\le|s|,|t|\le3000。

不难想到设 f_{i,j} 为 s_{1\sim i} 与 t_{1\sim j} 的最长公共子序列。

那么当 s_i=t_j 时有 f_{i,j}=f_{i-1,j-1}+1，否则 f_{i,j}=\max(f_{i,j-1},f_{i-1,j})。

输出方案只需要记录 f_{i,j} 从哪里转移过来，并在 s_i=t_j 的时候输出即可，注意要倒序。

时间复杂度 O(|s||t|)，可以通过此题。

G Longest Path 拓扑排序 DP

题意：给定一个 n 个点 m 条边的有向无环图，求 G 中的最长路径。

保证 2\le n\le10^5,1\le m\le10^5。

拓扑排序板子，我们设 f_u 为以 u 结束的最长路径长度。

如果 u 没有入边，那么 f_u=0，否则，f_u=\max_{\text{存在边 }v\to u}(f_v+1)。

时间复杂度 O(n+m)，可以通过此题。

H Grid 1 计数 DP

题意：给定 n 行 m 列的字符矩阵 a_{i,j}，如果 a_{i,j}=\texttt{.}，那么 (i,j) 就是空的，否则 a_{i,j}=\texttt{\#}，那么 (i,j) 就有墙。Taro 从 (1,1) 出发，不断向下或向右走到 (n,m) 且不能走过墙，求路径数对 10^9+7 取模的结果。

保证 2\le n,m\le1000，(1,1) 与 (n,m) 都是空的。

不难想到设 f_{i,j} 表示 (1,1) 到 (i,j) 的最小步数，如果 (i,j) 是墙那么 f_{i,j}=0，那么有：

其中 f_{0,i}=f_{i,0}=0,f_{1,1}=1。

答案为 f_{n,m}。

时间复杂度 O(nm)，可以通过此题。

I Coins 期望/概率 DP

题意：给定正奇数 n 和 n 枚硬币，第 i 枚硬币有 p_i 的概率正面朝上，1-p_i 的概率反面朝上。Taro 抛掷了这 n 枚硬币，求出正面多余反面的概率，需要保证绝对误差不大于 10^{-9}。

保证 1\le n\le2999,0<p_i<1。

不难想到设 f_{i,j} 表示抛掷了前 i 枚硬币，已有 j 个正面朝上的概率，那么：

时间复杂度 O(n^2)，可以通过此题。

J Sushi 期望/概率 DP

题意：给定 n 与长 n 的序列 a_i，每次操作独立等概率随机 [1,n] 中的位置，如果 a_i>0 将其减去 1 否则不变，求 a_i 全部变为 0 的期望操作次数，需要保证相对误差不大于 10^{-9}。

保证 1\le n\le300,1\le a_i\le3。

不难想到可以把 a_i=1,a_i=2,a_i=3 的 i 的数量记录到状态里，即设 f_{i,j,k} 表示 a 中有 i 个 1，j 个 2 和 k 个 3，其余全部为 0 时操作到 0 的期望次数，有：

现在考虑转移，有 i 个 1，j 个 2，k 个 3，剩下 n-i-j-k 个 0，那么就有：

1. 随机到 0：概率 \dfrac{n-i-j-k}n，对期望贡献 \dfrac{n-i-j-k}nf_{i,j,k}。
2. 随机到 1：概率 \dfrac in，对期望贡献 \dfrac inf_{i-1,j,k}。
3. 随机到 2：概率 \dfrac jn，对期望贡献 \dfrac jnf_{i+1,j-1,k}。
4. 随机到 3：概率 \dfrac kn，对期望贡献 \dfrac knf_{i,j+1,k-1}。

还要计入本次操作的贡献 1。

所以：

你发现左右两边都有 f_{i,j,k}，那怎么办，简单，把 f_{i,j,k} 移项：

然后就做完了。

时间复杂度 O(n^3)，可以通过此题。

这个题用记忆化搜索比较简单，移项也是期望 DP 经典套路。

K Stones 博弈论 DP

题意：给定正整数集合 A=\{a_1,a_2,\dots,a_n\}，还有 k 个石子，Taro 与 Jiro 交替地从 A 集合中选出一个数 x，并将石子数减去 x，不可将石子数减到 0 以下，不能行动的人输，Taro 先手，求出胜者。

保证 1\le n\le100,1\le k\le10^5,1\le a_1<a_2<\cdots<a_n<k。

博弈论经典套路：设 f_i 为有 i 个石子时先手是否必胜。

考虑从 i 能到达哪些石子数：

1. 如果这些石子数均是先手必胜，那么 f_i 就是先手必败。
2. 否则，f_i 就是先手必胜。

证明显然，注意如果 i<a_1 那么 f_i 时先手必败。

时间复杂度 O(nk)，可以通过此题。

L Deque 区间 DP

题意：给定 n 与长 n 的序列 a_i，Taro 与 Jiro 交替地从 a 中选出一个数 x，且必须位于 a 的开头或结尾，将 x 从 a 中删除，然后得到 x 分直到 a 变为空。设 X 是 Taro 的总分，Y 是 Jiro 的总分，Taro 希望最大化 X-Y，Jiro 希望最小化 X-Y，求出 X-Y。

保证 1\le n\le3000,1\le a_i\le10^9。

一眼区间 DP，设 f_{l,r} 为 a_{l\sim r} 的答案，那么，根据 n-(r-l+1) 的奇偶性我们可以知道现在是 Jiro 还是 Taro 操作：

边界条件当然是 f_{i,i}=\pm a_i（需要看谁先操作）。

题解做法是 f_{l,r} 表示 a_{l\sim r} 强制 Taro 首先操作，转移比较简单。

时间复杂度 O(n^2)，可以通过此题。

M Candies 计数 DP

题意：给定 n 与长 n 的序列 a_i，将非负整数 k 拆分为 n 个非负整数，第 i 部分需要在 [0,a_i] 之间，求方案数对 10^9+7 取模的结果。

保证 1\le n\le100,0\le k\le10^5,0\le a_i\le k。

我们设 f_{i,j} 为考虑了前 i 个数，前 i 个数之和为 j 的方案数，那么有：

直接暴力 DP 复杂度是 O(nk^2) 的，过不了，但是注意到：

时间复杂度 O(nk)，可以通过此题。

N Slimes 区间 DP

题意：有 n 个数 a_i，每次 Taro 可以选择两个相邻的数 x,y，以 x+y 的代价将其删除并在原位置插入 x+y，求将序列删除至只剩下一个数的最小代价。

保证 2\le n\le400,1\le a_i\le10^9。

我们设 f_{l,r} 表示将 a_{l\sim r} 删除至只剩下一个数的最小代价的最小代价，那么有：

考虑 f_{l,r}，枚举最后一次合并，假设是 a_{l,i} 与 a_{i+1,r} 合并，则：

时间复杂度 O(n^3)，可以通过此题。

这个题的最优时间复杂度是使用 Garsia–Wachs 算法，时间复杂度为 O(n\log n)，可以看文末。

O Matching 状压 DP

题意：给定 n 个左部点与 n 个右部点的二分图，左部点第 u 个与右部点第 v 个有边当且仅当 a_{u,v}=1，否则 a_{u,v}=0，求完美匹配数量对 10^9+7 取模的结果。

保证 1\le n\le21。

考虑状压 DP，设 f_{u,S} 为考虑了左部点中的 1\sim u，右部点已经匹配的集合为 S 的方案数，那么：

考虑枚举 u 匹配 v，那么：

时间复杂度 O(n^22^n)，会 TLE。

我们发现 u=\operatorname{popcount}(S)-1，所以可以丢弃 u 这一维。

时间复杂度 O(n2^n)，可以通过此题。

P Independent Set 树形 DP

题意：给定一棵 n 个节点的树，求树的独立集数量对 10^9+7 取模的结果。

保证 1\le n\le10^5。

我们设 f_{u,0} 为 u 子树内的最大独立集数量，且 u 节点不选，f_{u,1} 为 u 子树内的最大独立集数量，且 u 节点选，那么显然有：

时间复杂度 O(n)，可以通过此题。

Q Flowers 数据结构优化 DP

题意：给定长 n 的数组 a_i,h_i，保证 h_i 两两不同，选出若干下标 i_1<i_2<\cdots<i_k，在 h_{i_1}<h_{i_2}<\cdots<h_{i_k} 的情况下最大化 \sum_{j=1}^ka_{i_j}。

保证 1\le n\le2\times10^5,1\le h_i\le n,1\le a_i\le10^9。

不难想到设 f_i 为选择的最后一个下标为 i 的最大 \sum a_{i_j}，那么有：

直接暴力转移时间复杂度为 O(n^2)，会 TLE。

考虑用树状数组维护后半部分，每次查询 [1,h_i-1] 求出 f_i，然后将 a_i 位置修改为 f_i。

时间复杂度 O(n\log n)，可以通过此题。

R Walk 矩阵快速幂优化图上的计数 DP

题意：给定 n 个点的有向无自环图，求长 k 的不同路径条数对 10^9+7 取模的结果。

保证 1\le n\le50,1\le k\le10^{18}。

考虑设 f_{u,i} 为结束于 u，长 i 的不同路径条数，那么有：

时间复杂度 O(n^2k)，会 TLE。

考虑神奇的操作：将 f_{u,i} 视为一个列向量，就可以得到：

其中 M 为图的邻接矩阵。

那么我们就有：

注意到矩阵乘法具有结合律，那么可以用快速幂。

时间复杂度 O(n^3\log k)，可以通过此题。

S Digit Sum 数位 DP

题意：求 [1,k] 中各位数之和是 d 的倍数的数的个数对 10^9+7 取模的结果。

保证 1\le k<10^{10000},1\le d\le100。

首先改为求 [0,k] 之间满足条件的数的数量，最后再减去 1。

数位 DP 还是举个例子，以 k=114514 为例，我们将 [0,k] 的数分成这几类：

1. 114514
2. [114510,114513]
3. [114500,114509]
4. [114000,114499]
5. [110000,113999]
6. [100000,109999]
7. [000000,099999]

那么我们可以设计 DP 状态：f_{i,0/1,j} 表示考虑了高 i 位，是否全部与 k 相同，各位数之和模 d 等于 j 的方案数。

根据第二维的 0/1 我们可以知道这一位的范围，如果我们设 k 从高位到低位分别是 a_1 到 a_n，那么有：

时间复杂度 O(nd)，其中 n 是 k 的位数，可以通过此题。

T Permutation 排列计数 DP / 容斥 DP

题意：给定一个长 n-1 的字符串 s，仅由 > 与 < 组成，求满足对于所有 i\in[1,n-1]，如果 s_i=\texttt{>}，那么 p_i>p_{i+1}，否则 p_i<p_{i+1} 的排列 p 的数量对 10^9+7 取模的结果。

保证 1\le n\le3000。

Sol 1.

一个排列计数 DP 经典的套路：考虑如何构造每个排列，一个想法是按照前缀离散化后的序列 DP。

我们可以设 f_{i,j} 表示长度为 i 的排列中满足 s_{1\sim i-1} 的约束且 p_i=j 的排列数量。

那么将长 i-1 的排列插入一个数，就是选定 [1,i] 中的一个数 x 放到最后，然后将前 i-1 个数所有 \ge x 的数都加一。

那么这样我们就可以得到转移了：

边界条件 f_{1,1}=1，可以前缀和/后缀和优化。

时间复杂度 O(n^2)，可以通过此题。

Sol 2.

对大于号容斥，钦定集合 S 中的大于号不满足，剩下的大于号不用管，那么就剩下一些小于号和无限制，这样我们用广义组合数就算出来了。

对于容斥系数 (-1)^{|S|}，我们可以将其看作是 S 中的每个元素都贡献了一个 -1，那么就可以按照 S 中的元素从小到大 DP。

即，我们考虑设 f_i 为考虑了所有 S\subseteq[1,i] 的集合的带权方案数和，那么有：

其中 g_i 是 [1,i] 忽略所有大于号的方案数，这是容易计算的。

U Grouping 状压 DP

题意：给定 n 个点的带权完全图，将 n 个点分成若干组，当 i<j 在同一组内时获得 i\to j 的边权的价值，求最大价值。

保证 1\le n\le16,|a_{i,j}|\le10^9。

考虑状压，设 f_S 为 S 集合内的点分类的最大价值，转移考虑枚举最后一个选定的集合 T\subseteq S,T\neq\varnothing，然后更新：

其中 w_T 是 T 内部的价值，可以 O(2^nn^2) 预处理。

注意到，(S,T) 对只有 O(3^n) 种。

证明：注意到每个点只有三种可能：

1. 不在 S 中，不在 T 中。
2. 在 S 中，不在 T 中。
3. 在 S 中，在 T 中。

所以 (S,T) 对只有 O(3^n) 种，关键就是如何以 O(3^n) 复杂度枚举 (S,T)，这被称为子集枚举，如下代码可以做到：

for (int T = S; T != 0; T = (T - 1) & S) {...}

显然每次枚举的 T 都是 S 的子集，每个 T 都会被枚举到，这类似于减法。

时间复杂度 O(3^n)，可以通过此题。

V Subtree 换根 DP

题意：给定 n 个节点的树，对于每个节点 u 求包含 u 节点的连通子图的数量对 M 取模的结果。

保证 1\le n\le10^5,1\le M\le10^9。

遇到对所有节点求解同样问题的题，我们考虑换根。

首先考虑 u=1 怎么做，显然可以设 f_u 为 u 子树内包含 u 的连通子图的数量对 M 取模的结果，显然有转移：

对每个节点都做一遍的时间复杂度是 O(n^2)，会 TLE。

我们发现，每个节点 u 的 f_u 离正确答案仅差一步：父节点的答案。

所以我们在父节点处用全树的答案删去这一个子树的答案，然后作为父节点的答案传下去。

注意删除的时候要求前后缀积，模 M 下可能并非每个数都有乘法逆元（M 可能是合数）。

时间复杂度 O(n)，可以通过此题。

W Intervals 数据结构优化 DP / 线段树优化 DP

题意：给定 n 和 m 个区间 [l_i,r_i]，每个区间有一个权值 a_i，对于一个长 n 的 01 序列，如果其 [l_i,r_i] 区间内包含一个 1，其分数增加 a_i，求最大分数。

保证 1\le n,m\le2\times10^5,|a_i|\le10^9。

首先考虑暴力 DP，我们只需要记录最右边的 1 在哪里就可以了，即设 f_{i,j} 为考虑了前 i 个，最右边的 1 是第 j 位的最大分数。

转移：

考虑优化，首先把 r_k=i 的所有区间存储下来，那么 i 对 DP 数组的更新就是一些区间加，一个区间赋值，还需要维护区间最大值。

线段树维护即可，注意答案需要包含 f_{n,0}。

时间复杂度 O(n\log n)，可以通过此题。

X Tower 确定转移顺序

题意：给定 n 个三元组 (w_i,s_i,v_i)，选出若干个三元组并以任意的顺序排列这些三元组，需要保证每个三元组前面 w_i 之和小于等于 s_i，最大化 \sum v。

保证 1\le n\le10^3,1\le w_i,s_i\le10^4,1\le v_i\le10^9。

首先直接 DP 是不好做的，因为顺序不好确定。

既然顺序不好确定，那么我们就规定顺序，比如考虑这个情况：

前面 \sum w=W，接上 (w_1,s_1),(w_2,s_2)，那么合法当且仅当 \begin{cases}W\le s_1\\W+w_1\le s_2\end{cases}，这等价于 \begin{cases}W\le s_1\\W\le s_2-w_1\end{cases}。

如果我们要确定一个转移顺序，那么我们就应该找到一个全序，使得如果 2,1 顺序可以，那么 1,2 顺序也可以，这要求：

显然 W\le s_1-w_2\implies W\le s_1，要从 \begin{cases}W\le s_2\\W\le s_1-w_2\end{cases} 推出 W\le s_2-w_1，我们必须有 s_1-w_2\le s_2-w_1，也就是 s_1+w_1\le s_2+w_2。

所以我们按照 s_i+w_i 升序排序，排序完了做背包就可以了。

时间复杂度 O(n\log n+n(\max w+\max s))。

数组开到 2\times10^4，最下面一层 w 可以任意大。

Y Grid 2 容斥原理设计 DP

重题：P4478 [BJWC2018] 上学路线 和 CF559C Gerald and Giant Chess。

题意：给定 n\times m 的网格中的 k 个障碍 (x_i,y_i)，求 (1,1) 到 (n,m) 不经过障碍的路径条数对 10^9+7 取模的结果。

保证 1\le n,m\le10^5,1\le k\le3000。

考虑正难则反，求出 (1,1) 到 (n,m) 不经过障碍的路径条数，然后减去经过障碍的路径条数。

我们对于每条经过障碍的路径，强制在第一次经过障碍时计数，后面不管。

首先把障碍按照 x 坐标为第一关键字，y 坐标为第二关键字排序，然后设 f_i 为从 (1,1) 走到第 i 个障碍，只经过了第 i 个障碍的方案数，这是容易计算的：

我们把 (n,m) 也看做一个障碍点，那么答案就是 f_{k+1}。

时间复杂度 O(n+m+k^2)，可以通过此题。

Z Frog 3 斜率优化 DP

题意：给定长 n 的序列 h_i，Frog 每次可以从 i 跳到任意 i<j\le n 的位置，花费 (h_i-h_j)^2+C 的代价，C 为给定常数，求 1 到 n 的最小花费。

保证 2\le n\le2\times10^5,1\le C\le10^{12},1\le h_1<h_2<\cdots<h_n\le10^9。

朴素的 O(n^2) DP 是显然的：

考虑优化，首先拆代价：

将 f_j+h_j^2 看作 y，h_j 看作 x，我们要维护一个集合，支持插入 (x,y)，查询 y+ax 的最小值，保证 a 单调递减且均小于 0，保证 x 单调递增。

容易发现只有下凸壳是有用的，那么用一个单调队列维护下凸壳，每次只需要用 -2a_i 这个斜率弹掉前面的点，求出 f 后再弹掉后面的点就可以了。

时间复杂度 O(n)，可以通过此题。

当然维护凸壳是分类的，比如：

在后面写点啥呢，不如写点 ABC 优质 DP 合集。

本文中，定义优质 DP 为我觉得思路不常见的题。

ABC232E Rook Path

题意：给定 n\times m 的网格，棋盘上 (x_1,y_1) 有一个棋子，每次这个棋子可以移动到 x 坐标相同 y 坐标不同的位置或 x 坐标不同 y 坐标相同的位置，求 k 次后移动到 (x_2,y_2) 的方案数。

保证 2\le n,m\le10^9,1\le k\le10^6,1\le x_1,x_n\le n,1\le y_1,y_2\le m。

暴力 DP 就是设 $$

代码

点这里。

Garsia–Wachs 算法解决 N Slimes

参考了 OI Wiki。

我们考虑这个算法：

给出了数组 a_{1\sim n}，表示需要合并的数，我们令 a_0=a_{n+1}=\infty，重复进行 n-1 次：

首先找到一个 k 满足 a_{k-1}\le a_{k+1}，记录 X=a_k+a_{k+1} 然后我们将 a_k,a_{k+1} 合并。 找到 j\in[0,k-2] 满足 X\le a_j，然后将 X 插入到 a_j 之后。

这个算法可以得到最优解，并且时间复杂度是 O(n^2)，用平衡树可以做到 O(n\log n)。

证明看这个吧，毕竟这真的不是本文的重点。