2019 年电子科技大学 ACM-ICPC 暑假前集训动态规划专题解题报告

8/12/13

我 J 真的写不出来了……

A. oy 环游世界

题目描述

有 n 个城市，第 i 个城市坐标为 (x_i,y_i)，定义两城市之间距离为两城市之间的曼哈顿距离，求从制定城市 s 出发遍历所有城市的最少代价，最后终点任意。

数据范围：1 ≤ n ≤ 17。

题解

TSP 板子，但是与 TSP 的唯一区别是不需要回到起点，稍微改动一下即可。

记 S 为目前到过城市的状态，每次枚举一个到过的城市与未到过的城市，更新最短距离即可。利用记忆化搜索或用深度优先搜索实现 DP 过程也可。

记 f_S, i 为已经到过的城市状态为 S，到过的最后一个城市为 i，则 DP 的转移方程为：

时间复杂度 𝒪(2ⁿn²)，空间复杂度 𝒪(n2ⁿ)。

代码见这里

B. 挖矿攻略

题目描述

n × m 网格中每格点有两种权 a, b，现每个点必须向上或向左转移权值，将权值加在目标点上，但每次转移的贡献只是两种点权中的一种，求经过转移后最上和最左边点的权值和。

数据范围：1 ≤ n, m ≤ 500。

题解

考虑对于一个点的转移，如果这个点点权选择向左传递，那么它左边的点均向左转移，否则，它上面的的点均向上转移。这是一种贪心的思路，如果在传输过程中转换传递方向，将会丢失一种点权中的一部分，这比全部取同一种点权要劣，因此这种贪心是可行的。

记 f_i, j 为到达点 (i,j) 时以 (i,j) 为矩形右下角的矩形区域中获得的最大点权。按照这种贪心思路，f_i, j 是由 f_{i, j − 1} 或 f_{i, j − 1} 通过扩展矩形的一列或一行得到的，不难写出如下转移方程：

对于两个求和式，可以利用前缀和优化转移，降低时间复杂度。

时间复杂度 𝒪(nm)，空间复杂度 𝒪(nm)。

（其实感觉不用优化转移 𝒪(n³) 也能过……）

原题详见：Luogu 2780. 狗哥采矿

代码见这里

C. 手办

题目描述

有 n 个手办，每个手办高度为 h_i，现从 n 个手办中最多取出 k 个，然后插回序列中。定义一个序列的混乱度为一个序列中高度相同的子串的个数。求这样整理可以达到的最小混乱度。

数据范围：1 ≤ k ≤ n ≤ 100, 114514 ≤ h_i ≤ 114521。

题解

注意到手办数较多，但高度种类很少，可以考虑对高度进行状压 DP。考虑到一个性质，如果序列中存在一个手办与要插入的手办高度相等，则可以把这个手办插入到序列中与这个手办高度相等的手办旁边，这样不影响答案，否则为了避免插入影响到已有段的连续性，只能放在后面或两相邻段中间，但是答案总是加一。于是，我们可以采用先用 DP 计算抽取过后剩余序列的最小混乱度，再把手办补回来更改答案的方式解决这个问题。

据此，设状态 f_{i, s, j, p} 为处理到第 i 个位置，目前手办高度状态为 s，已经取出了 j 个手办，目前 1 ∼ i 序列中最后一个手办高度为 p 的最少操作次数。可知有三种转移：

1. 第 i 个手办和第 i − 1 个高度相同，则：

2. 第 i 个手办和第 i − 1 个高度不同，且被抽掉，则：

3. 第 i 个手办和第 i − 1 个高度不同，但没被抽掉，则：

其中 p 是在 s 集合中出现的高度，s 可以通过枚举 1 ∼ i 所有手办的高度集合得到。

最后，枚举 f_{n, s, j, p}，考虑所有出现的高度 S 与 s 的差集大小加入答案，取最小值即可。这里差集可以通过求 S ⊕ s 中 1 的个数获得，⊕ 为异或运算，求 1 的个数可以利用 __builtin_popcount() 函数。注意到 DP 方程只与前一个位置有关，因此可以利用滚动数组优化空间。

时间复杂度 𝒪(nkh2^h)，空间复杂度 𝒪(nh2^h)，其中 h 为序列中高度的种类数，h ≤ 8。

原题来自：

• UVa 12235. Help Bubu；
• HDU 3237. Help Bubu。

题外话：这道题是敝校 NOIP 训练题，但是因为偷懒当年没写，两年半后还是还了……

（悬殊的 RunID 差距……）

代码见这里

D. 序列

题目描述

给定一个长度为 n 的序列，求其中对称的长度最长的山峰形子序列。这个山峰必须有尖峰。

数据范围：1 ≤ n ≤ 10⁶。

题解

考虑这个山峰的每一半，都是求一个最长上升子序列，所以我们正着做一次 LIS，倒着做一次 LIS，然后枚举每个点，取以这个点为结尾的正向与逆向最长上升子序列长度的最小值，然后乘二减一即可。

LIS 有优秀的 𝒪(nlogn) 做法，但是不知道为啥二分写挂了于是怒而 lower_bound……

时间复杂度 𝒪(nlogn)，空间复杂度 𝒪(n)。

代码见这里

E. 神

题目描述

给定一个长度为 n 的小写字母串，按顺序每 k 个分成一块，块内可以重排，块间不能排序，求最少段数，段数和 C 题中的定义一致。共 T 组数据。

数据范围：1 ≤ T ≤ 100, 1 ≤ k ≤ n ≤ 10³，保证 n 是 k 的整数倍。

题解

考虑块内一段，最小段数为出现的字符种数，即把所有相同的字母放在一起为最优解。再考虑块间排序，可以证明，如果两块之间存在相同字母，那么这两块间答案为两块的答案和减一，最后考虑相邻三块之间的排序，如果三块都有相同字母，那么将中间一块的相同字母全部放前，放后和分开放置的答案是相同的，因此无需考虑分开放置的情况。

记 f_i, j 为前 i 块已经排好序后，最后一块的末尾为 j 的最少段数。不难写出如下转移：

f_i, j = min {f_{i − 1, k}+a_i−[k∈S_i]}

其中，a_i 为第 i 块出现字母种数，S_i 为第 i 块出现的字母集合，[] 为 Iverson 括号。需要注意只有一段的情况转移与多于一段的情况有区别。考虑不分开放置（如果考虑分开放置的话还需要考虑一块中字母出现次数），那么多于一个字母的情况需要块内开头和结尾字母不同，否则会答案有误。

最后答案是 min_i ∈ Σ{f_m, i}，其中 Σ 为字符集。

时间复杂度：𝒪(T×|Σ|²n)，空间复杂度：𝒪(|Σ|n)。

代码见这里

F. 苇名欧一郎

题目描述

一共有 n 个敌人，最初可以捶死一些敌人，捶死每个敌人之前需要捶死一些敌人之一，要求捶遍所有敌人，求捶人顺序有多少种。一共有 T 组数据。

数据范围：1 ≤ T ≤ 50, 1 ≤ n ≤ 16。

题解

这道题是比较经典的拓扑序计数问题。记 f_s 为目前捶人状态为 s，捶成这种状态的顺序数。考虑再捶一个没捶过的人 i，判断一下是否已经锤过了一个为了锤他需要捶的人，或者是否是最初就可以捶掉他，然后转移一下即可：

其中，d_j 是为了捶 j 要捶的敌人集合。

时间复杂度 𝒪(Tn2ⁿ)，空间复杂度 𝒪(2ⁿ)。

代码见这里

G. 子串

题目描述

给出长度为 n 的数字串，请求出其中能被 k 整除的子串个数。

数据范围：1 ≤ n × k ≤ 2 × 10⁷。

题解

虽然不是数位 DP 但是可以用类似思路解决。记 f_i, j 为以第 i 位结尾，得到子串对 k 取模为 j 的方案数。那么不难写出扩展一位得到的子串方案数：

注意先需要将所有长度为 1 的子串计入 DP 数组。

最后答案是 。

注意到这道题 n, k 范围不固定，但是 nk ≤ 2 × 10⁷，因此开数组的时候可以采取 vector 嵌套或者开成一位数组，通过计算将二维数组的坐标映射到一位数组上。

帮着测出了数据范围有问题的能不能给点加分啊

时间复杂度 𝒪(nk)，空间复杂度 𝒪(nk)。

（当然通过滚动数组和动态开数组可以做到 𝒪(k) 的空间复杂度）

代码见这里

H. van 游戏

题目描述

树上有权值，两人在树上博弈，一个人的策略是保证自己获得的权值尽可能大的情况下，对方获得尽可能小的权值，另一个人的策略是保证对方获得权值尽量小的情况下，对方获得尽可能大的权值。求最后两人获得权值之和。

数据范围：1 ≤ n ≤ 10⁶, 1 ≤ x_i ≤ 10⁹。

题解

看到博弈论就不想做的就是我了……

首先看上去是树形 DP，再看一眼确实是树形 DP。

记 f_i 为两人取完以 i 为根的子树后获得的权值。对于第一种策略，选择子树中第一个值尽可能大的进行转移，如果有相同的，取第二个值小的转移；对于第二种策略，选择子树中第一个值尽可能小的进行转移，如果有相同的，取第二个值大的转移。

需要注意的是，当用搜索写树形 DP 时需要注意选择的人和这一层是谁拿的恰好相反。

时间复杂度 𝒪(n)，空间复杂度 𝒪(n)。

代码见这里

I. 攻略妹纸

题目描述

有 n 个物品装入体积为 m 的背包，每个价值 a_i，体积是 y × max {c_i − b_i, 0}，另有附加限制，如果装入背包的物品中最大的 d_i 小于 k，则需额外占体积 x × (d_i−k)，求最大价值。

数据范围：1 ≤ n, m ≤ 5 × 10³。

题解

如果去掉这个附加限制，就是一个 01 背包。

考虑这个附加限制，显然对于 d_i 确定的情况，额外占的体积是一定的，那么我们可以预支出这一部分体积，并对 x(d_i−k) 从小到大排序，保证后更新的状态一定可以基于前面的状态得出。这样再做 01 背包即可满足附加限制了。

注意数据范围要开 long long……

时间复杂度：𝒪(nm)，空间复杂度 𝒪(m)。

代码见这里

J. 扫广场

题目描述

下一站，下一站，是人民扫广场

给出一个 n × m 的 01 矩阵，求将多少个 1 改成 0 就能使得所有 0 是是四连通的。

数据范围：1 ≤ n × m ≤ 80。

题解

五进制状压加优化我佛了，插头 DP 显然过了。

数据十分有毒，我第一遍 WA5 之后改了个大 bug 之后 WA4，调完 WA1……

我也不知道 cjj Sugarrr 两位神仙怎么 A 过去的，LoliconAutomaton 说想写网络流但是不知道怎么建源汇点，我也想网络流但是感觉有毒，Decision 大爷 WA8 之后可能是被我数据毒到了，我写了九个小时啥用没有心态是真的炸了……

不知道以后会不会补，反正先这样吧……

已知 n × m ≤ 80，根据基本不等式，min {n, m} < 9，所以我们可以把最小的当做列，根据连通性进行状态压缩。最大只会有四个连通分量，形如 10203040 这样，因此我们采用五进制状态压缩，把所属连通分量的编号作为状态，还有 0 作为这个格子被占用的情况。

然后对于每一行，枚举上一行状态和这一行状态，如果匹配合法则进行转移。就是这里判断合法十分难受，有很多特殊情况，还有全 0 的情况，第一行情况，我可能是这里写炸了就不说了……

但是这样复杂度就炸了，枚举行 𝒪(n)，枚举上一行状态 𝒪(5^m)，枚举这行状态可以写成子集枚举 𝒪(2ⁿ)，还有判断可行的复杂度 𝒪(m)，直接变成 𝒪(nm10^m)，复杂度炸了。

注意到 10203 和 10302 这两个状态是本质相同的，11223344 这样的状态是本身不合法的，因此存在很多无用状态，我们可以把它们剪掉。出题人 oydy 剪到了不到 200，cjj 剪到 697，我剪到 2400+，但是只有我挂了……

但是这样复杂度就不炸了，就可以尽情 WA on 1 了……

最后发现我构造状态像 cxk，直接枚举每个五进制状态然后判断一下合不合法就完事的事情被我硬生生的搞成了一个暴搜，还搜不出来最优的……

实际上最后一次改的匹配合法状态和生成下一行状态是对的但是直接被我删了还没留备份……

时间复杂度 𝒪(nmk2^m)，空间复杂度 𝒪(nk)，其中 k 为合法状态数。

代码见这里

K. 抽卡

题目描述

玄学抽卡，每次有 x 的概率单抽出奇迹，一共有 m 个碎片，有 y 的概率出一个碎片，但是只有集齐 m 个碎片才能合成。问 n 次之内出货的概率。

数据范围：n ≤ 10⁹, m ≤ 100。

题解

看题来说，能猜到是矩阵快速幂优化概率 DP，并且能猜到复杂度是 𝒪(n³logn) 的……

可以把单抽奇迹的情况考虑成一次补齐所有碎片，记 f_i, j 为前 i 次一共出了 j 个互不相同的碎片的概率。对于 1 ≤ j < m 有如下转移：

f_{i + 1, j} = [1−x−(m−j)y]f_i, j + (m−j+1)yf_{i, j − 1}

对于 j = 0 只有一种转移：

f_{i + 1, 0} = (1−x−my)f_i, 0

对于 j = m 有：

于是我们将其写为矩阵，记为 A，则：

DP 矩阵如下：

其实 DP 矩阵只是一个列向量，但是为了偷懒矩阵乘法不想写那么多于是扩展成 m 阶方阵了……

这样答案就是 A^n − 1 × f 中坐标为 (m,0) 的元素了。

读入为了避免精度误差直接用整数形式读入，也不用最后乘 1000ⁿ 了。

感谢出题人没出 x = 1 或者 y = 1 的数据但是 n = 0 是什么鬼数据下限不写的时候要考虑全……

时间复杂度 𝒪(m³logn)，空间复杂度 𝒪(m²)。

代码见这里

L. zh 的奖杯

题目描述

给了 n 个物品，每件物品容量为 v_i，每次选取一段连续物品放入箱子里。如果第 i 到第 j 个物品被放在箱子里，代价是 ，记代价为 x，花费是 (x−L)²，求一个把所有物品装箱的最小花费。

数据范围：1 ≤ n ≤ 5 × 10⁴, 1 ≤ v_i, L ≤ 10⁷。

题解

对于这道题，有一个显见的 DP 转移方程。记 f_i 为将 1 ∼ i 的物品全部装箱的最小花费。那么转移方程为：

其中，s_i 为 v_i 的前缀和。

易知，这个状态转移得到的 DP 时间复杂度为 𝒪(n²)，过不去。

继续观察转移方程，令 g_i = s_i + i, c = L + 1，这个转移方程即可写作：

很朴素的想法是，只要 |g_i−g_j−c| 很小，也就是 g_i − g_j 距离 c 越近越好，那么这样的话，当 f_i 要采取决策的时候，决策点位置应该在 f_j 的决策点之后，如果在 f_j 的决策点之前，由于 v 恒正，记决策点为 x，那么 g_i − g_x 的值就会距 c 变大，因此决策具有单调性。

网上其实有很多证明黄学长也写过但是不想打唉算了还是打吧

下面考虑证明这一决策单调性，假设 i 位置在 k 位置的决策优于 j 位置时 k > j，那么根据 DP 方程，有：

f_k + (g_i−g_k−c)² < f_j + (g_i−g_j−c)²

对于决策单调性，需证对所有 i 之后的状态 x，都有：

f_k + (g_x−g_k−c)² < f_j + (g_x−g_j−c)²

由已知，f_x = f_i + δ，其中 δ > 0。代入上式：

f_k + (g_i−g_k−c+δ)² < f_j + (g_i−g_j−c+δ)²

左右两边展开，得：

由于 v > 0 恒成立，那么 g 为单调递增数列，由于 k > j，则 g_k > g_j，即 g_i − g_k − c < g_i − g_j − c，由 δ > 0 知 2(g_i−g_k−c)δ < 2(g_i−g_j−c)δ，结合假设，与展开后大柿子符合，因此符合决策单调性。

现在的关键就是怎么利用决策单调进行转移。

我们将第一个不等柿平方打开：

f_k + g_i² − 2g_i(g_k+c) + (g_k+c)² < f_j + g_i² − 2g_i(g_j+c) + (g_j+c)²

移项，将 g_i 移至一边，注意 k > j，得到：

这就是 k 位置转移优于 j 位置时情况。

根据决策单调性，我们可以维护一个单调队列来维护 g_i，先把不优的状态弹掉，转移队头，然后把目前的状态插入队列尾并维护单调性。相当于维护一个单调增的队列。

题外话：先卡精度，然后加大数据范围之后爆 long long 了，但是过了……

原题来自：HNOI 2008. 玩具装箱

时间复杂度 𝒪(n)，空间复杂度 𝒪(n)。

代码见这里

M. 崭新龙狙，制霸全区

题目描述

记 f(i) 为数字 i 中出现 4750 的次数，求 。

数据范围：1 ≤ L ≤ R ≤ 10¹⁰⁵。

题解

典型数位 DP，考虑 ，那么答案就变成了 g(R) − g(L−1)。

考虑记忆化搜索，记状态 S_x, p, l 为搜索到第 x 位，在 x 位之前已经匹配了 p 位的状态，l = 1 为上一位已到枚举上限，否则未到上限。然后根据上一位是否达到上限枚举数字转移。

每当枚举到 S_x, 4, l 这样的状态时，说明出现了一段连续的 4750，于是我们要处理答案了。当 l = 1 时，由于已经到了枚举上限，所以加入的答案为第 x 位之后的数字串组成的数字，否则加 10^L − x，其中 L 为数字串的长度。

这是第二次写数位 DP……

时间复杂度 𝒪(kn)，空间复杂度 𝒪(n)。其中 k = 10。

代码见这里