1 月做题记录

 

一点动态规划：

动态规划基础 - OI Wiki

---

[ABC339E] Smooth Subsequence

dp 式子是可以看出来的。设 为在以位置 结尾的最长光滑序列的长度。

于是式子可以列出来：

$$dp_i = \max_{j<i \land a_j \in [a_i-D, a_i + D]}(dp_j + 1)$$

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是开始优化：这里使用线段树优化。创建一个值域线段树。对于值域线段树的位置 ，存储的是 。于是我们每次只用查找在位置 里面的最大值，然后加上 就是 了。最后只需要求 序列的最大值。

时间复杂度 。

Double Exp: Flat Subsequence

---

[ABC353G] Merchant Takahashi

Tips：最开始高桥的初始位置为村庄 。题目翻译忽略了这一点。

设 为赶了第 次集所持有的钱数。因为钱数可以为负数，所以最开始先 memset dp 序列为负无穷，。

然后得出 dp 转移式子：

$$dp_i = \max_{j < i} (dp_j - |t_i - t_j|)) + p_i$$

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是开始优化：这个绝对值是非常烦的鬼玩意，于是我们将绝对值拆开：

$$dp_i =p_i + \max \left\{ \begin{aligned} dp_j - t_i + t_j) &(t_j \le t_i)\\ dp_j - t_j + t_i) &(t_j > t_i) \end{aligned} \right.$$

于是我们可以将其转移到线段树上。节点 存储两个东西：

$$pre_{t_x} = dp_x + t_x\\ suf_{t_x} = dp_x - t_x$$

然后每次查询的时候就查 的 的最大值减去 ，再查 的 的最大值加上 ，然后两者取 ，最后加上 就得到 了。

最后答案还是整个 序列的 。时间复杂度 。

---

Linear Kingdom Races

这道题是一种新的设 DP 状态的一道基础题。

跟 THUWC 2025 D1T1 比较像（给我气笑了(╬▔皿▔)╯）。

还是先设 dp 状态。设 为修复了前 条路的一些路，所得到的最大收益。

于是可以得出下列转移式子：

$$dp_i = \max(\max(dp_j + 在 [j+1, i] 的区间收益), dp_{i-1})$$

第一项就是修 的路所带来的钱值的变化，第二项就是啥都不修，光吉猛修。

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是考虑优化：还是把它搬到线段树上。每一个线段树节点 存储 ，所以这个东西是随着 实时更新的。当 为某个区间 的终点的时候，就把这颗线段树的 全部加上 。

然后就和平常的线段树优化一样搞就可以了。时间复杂度 。

---

P9871 [NOIP2023] 天天爱打卡

这道题是上一道题的升级版。就是加了一个 的限制条件和范围为 的 。后者可以用离散化解决，前者就用双指针 来维护。这里的 表示连续跑步范围边界。当 时， 自加，知道连续跑步的时间小于等于 天。

---

Intervals

设 为考虑区间范围 ，最后一个 放置于 处的答案。

于是可以得出：

$$dp_{i ,j} = \max_{x \in [1,j]}(dp_{j,x}) + 在 [1,i] 区间内包含点 j 的区间所带来的贡献$$

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是考虑优化：建一个线段树，线段树的每一个节点 表示考虑区间 时，的 。这棵线段树是随着 的改变而改变的。每一次遇到以 为终点的区间时，将线段树区间 加上该区间的值。然后第一维 的最大值就是 。

时间复杂度 。

---

[AGC044E] Random Pawn

学长讲题一则。

题目描述的不是很清楚，我在这里重新描述一下：

有一个长为 的环，环上的每一个位置上面有权值 和代价 。一开始你会在这 个位置随机一个位置作为起始点。每次你到一个点 的时候，你有两种选择：

• 继续走其他点，你会随机到达这个位置的相邻的两个位置的其中一个。你会花费 的代价。

• 在该点停止，并且获得该点的权值 ，游戏结束。

求最大的期望价值。

首先我们设在点 获得的最大期望价值为 。

一个环上是不好搞的，于是我们要先拆环为链。

又因为，在这道题很容易发现的、如果一个位置它的值是这个序列最大的，那么我们也就没必要跳到其他点去得到更小的值。

于是我们就设这条链的两端就为这个最大值，再以这个最大值为开头重新排列。于是把长为 的环拆为了长为 的一条链。（同时 序列也重新排列。）

为了更好的描述，下面把 。

于是就可以得到：

$$\left\{ \begin{aligned} &f_0 = a_0, f_n = a_n\\ &f_i = \max(a_i, \frac{f_{i-1} + f_{i+1}}{2} - b_i) (i \neq 0 \land i \neq n) \end{aligned} \right.$$

我们发现后面的那一坨 很烦，我们现在要把它给消掉。

设 。

于是原式就变为了：

$$\left\{ \begin{aligned} g_0 &= c_0, g_n = c_n\\ g_i &= \max(c_i, \frac{f_{i-1} + f_{i+1}}{2} - b_i + d_i) (i \neq 0 \land i \neq n) \\ &= \max(c_i, \frac{g_{i-1} + g_{i+1}}{2} + \frac{d_{i-1} + d_{i+1}}{2} - b_i + d_i) \end{aligned} \right.$$

然后为了消掉这个烦人的 ，就要使 。那么它的递推式就是：

$$d_{i+1} = 2(b_i - d_i) - d_{i-1}$$

于是我们随便设 和 ，然后后面的 就可以通过这两个 和整个 序列推出来。

于是就变为了：

$$\left\{ \begin{aligned} g_0 &= c_0, g_n = c_n\\ g_i &= \max(c_i, \frac{g_{i-1} + g_{i+1}}{2}) (i \neq 0 \land i \neq n) \end{aligned} \right.$$

发现 的转移式后面的那个玩意像中点公式，于是就可以把它转移到二维平面上：

每一个 在二维平面上就转移成了点 。如果不考虑 ，那么每一个点就是它的左右两个点的中点，整个 序列在二维平面上会变为一条线段。

现在， 来了。如果这个时候的 大于这个时候的在线段上的值，那么就将这个 值在线段上的点拔高至 。

具体地、

最开始有两个点， 和 。现在 来了。因为不大于这个时候的线段最大值 ，所以 ：

现在，第二个点 来了。它因为大于这个时候的线段最大值，所以就把 的值拔高到 ，同时修改 ：

然后第三个点 ，因为它不大于这个时候 的值，所以它的值是 ：

第四个点 。很明显它大于这个时候的 。所以拔高，，同时修改 ：

最后，我们发现，这玩意其实就是一个凸包。我们就求凸包推出 序列，再从 反推回 。最后因为是随机的一个起点，所以最后答案是整个 序列的平均值。

---

[ABC389E] Square Price

ABC 389。这场我打了 1147 名。恶臭，E 题比 F 题难。

因为购买 个第 种商品开销 元，所以可以看作每买第 个第 种商品开销 元。

那么我们就可以贪心选了。在这 种商品里面选开销最小的选，然后一直选到不能选为止。

但是暴力做是可以构造一组价格全是 ， 的数据来卡你的。所以要优化。

我们枚举我们能买到的最大价格 。就相当于是，价格为 及以下的商品全买。价格为 及以上的不能全买（但是可以买一些）。我们用二分搜索可以 查找出来这个 。然后再 遍历每一个商品，看看有没有并且能不能买价格为 的商品。如果有就买。

于是这道题就做完了。

---

[ABC389F] Rated Range

原神题。

有了数据结构，就不需要脑子了！

因为值域是在 ，于是我们就可以开一棵线段树，每个线段树的节点 表示的就是初始 Rating 为 时，经过这些 Contest 之后它的最终 Rating 是多少。

因为不管举行多少次，不管加分的 Rating 范围是多少，最终的序列一定是单调的。于是我们就可以线段树二分找到要修改的最小下标和最大下标。然后区间加。最后查询的时候就查线段树上的叶子节点就行了。

所以这道题其实是线段树上二分板子题。然后就做完了。

---

P4159 [SCOI2009] 迷路

这道题如果没有边权，那么这道题就是邻接矩阵快速幂板子。但是现在有边权。

于是因为边长在 之间，所以可以把一个点拆成 个点。我们设这九个点为 。

然后初始时 向 连边。

当我们要连边 时，就可以从 连到 。因为 向 距离为 ，再加上 到 的边，那么距离刚好就是 。然后就可以用邻接矩阵快速幂做了。

快速幂复杂度 。

---

Power of Matrix

这道题让我们求 。 太大，那么就用分治。

• 当 为偶数的时候，那么设 ，那么原式就为 。

• 当 为奇数的时候，那么设 ，原式就为 。

然后就可以分治做了。

---

P2886 [USACO07NOV] Cow Relays G

离散化后的邻接矩阵快速幂。

但是这里使用的是 Floyd 算法，所以要将乘号重定义。

---

The Battle of Chibi

这道题还是 dp。

设 为以 结尾的，长度为 的严格上升子序列的个数，那么就有转移式子为：

$$dp_{i, j} = \sum_{k < i \land a_k < a_i} dp_{k, j-1}$$

初始状态设 。

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是开始优化：可以用树状数组优化。因为求的是前缀和。但是值域太大，需要先离散化。

时间复杂度 。

---

P2605 [ZJOI2010] 基站选址

这道题依然是一道 dp。

开始设状态：设 为将第 个通讯基站设在 位置、并且只考虑区间 时，需要花费的最小钱数。那么就可以开始转移：

$$dp_{i, j} = c_i + \left\{ \begin{aligned} &\text{将基站设置在位置 i 时前面没照顾到的人要赔的钱} &(j = 1)\\ &\min_{l < i}(dp_{l, j-1} + \text{将基站设在位置 k, i 时中间没照顾到的人要赔的钱}) &(j > 1) \end{aligned} \right.$$

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是考虑优化：我们首先求出对于村庄 ，这个村庄能允许的修基站的范围 ，超过这个范围，你就要赔钱。

然后当 时，因为这个是个带范围的 式，所以可以将其搬到线段树上去做。

具体地、首先将上一个 的 dp 状态搬到线段树上，即节点 设初始值为 。然后每次算完 时，就可以看哪些范围 的 值为 。若存在，就在节点 区间加上该区间对应的 。然后算 就直接查区间 即可。

而当 时，方法就不一样，但思路是类似的。因为这是建的第一个基站，所以就不存在什么 一说。而赔的钱，自然也就是把基站建在 的前面所有在范围外的村庄的赔的钱的总和了。

---

P3287 [SCOI2014] 方伯伯的玉米田

这道题也是一道 dp。用人话来说，就是可以执行最多 次区间加 。然后求最长单调不下降序列。

我们还是先设 dp 状态：设 为以 结尾，并且 被拔高了 次所构成的最长单调不下降序列。

我们能发现一个性质：就是你要拔高一个区间，那么拔 肯定是最优的。因为如果你不是以 结尾，那么中间的数和右边的数的相对大小关系就会改变，就会使右边的数相对中间的数变小。这样肯定是不优的，因为我们要求最长单调不下降序列。

然后就可以得出 dp 转移式：

$$dp_{i, j} = \max_{p < i, q \le j, a_{p} + q \le a_i+j}(dp_{p, q})+1$$

（不用考虑是不是不连续了，因为反正中间的那些你都不管，那么根据之前的性质，就让它加上 。）

但是，直接用这个鬼玩意的复杂度是 的，过不了此题。

于是考虑优化：我们可以看到转移式是个 式，限制条件有 个（其实从左到右枚举可以消掉第一个变成 个）。然后如果只有 个限制条件就可以把它放到树状数组上做，那现在 个限制条件就可以把它放到 维树状数组上做。

于是这道题就做出来了，时间复杂度 。

---

Codeforces 2063-D

这道题赛时想到了思路，但是因为时间不够没有调出来。然后掉到了 1800 多名去了（Codeforces Round 1000）。Yee tour fen.

容易发现，选线段肯定是选最两边的，选点肯定是选最中间的。这样是最优的。那么我们首先给点排序（题目里没说序列有序！！），然后就可以开始贪心选：每次选线段就比较一下 侧的两端的距离和 侧两端的距离。然后选最长的那一端，假设为 端。然后把两端的两个点和 端的中间的那一个点给删掉。然后把这个三角形记录到 栈里面（栈的作用后面再说）。如果在 端同理。

但是这个时候，你会遇到在 端选完了，但是 端还剩一堆点的情况。这个时候因为还没有达到 ，所以肯定是要强制选对面的一些点的。那么我们就从 栈里面弹出来一个三角形（就是删除一个三角形。根据从大到小选的原则，这个三角形是面积最小的）。这样就给对面的点创造出来了 个 点。然后对面的 个 点再和这 个 点相组合，就是 个新的三角形。再减去弹出来的那个三角形，就相当于这就是多了一个三角形的最优答案。

那么边界 如何算？这个其实是好算的。设最终选的最多次在 端选了 条线段，在 端选了 条线段。

那么就可以列出不等式：

联立可得 。

又因为两侧选点的极限是 ，所以 。

于是这道题就做完了。

---

AT_dp_s Digit Sum

从这里开始似乎就都是 AT_dp 比赛的题了。

这道题一眼数位 dp。

首先设状态：设 为在没有到边界的情况下，当前面的数的总和 时，并且取的上一个数为 ，并且还剩下 个数没有取时的答案。然后像一般的数位 DP 记忆化 + 转移即可。

---

AT_dp_t Permutation

这道题的 DP 状态比较巧妙。

设 表示现在一共填了 个数，并且刚刚新加进来的数是在这 个数里面从小到大的第 个。

为什么这么设状态呢？因为其实这些大于号小于号是用来限制它们的相对大小关系的。只要相对大小关系对了，怎么填都可以。

于是我们就可以轻松得出式子：

$$dp_{1, 1} = 1$$ $$dp_{i, j} = \left\{ \begin{aligned} &\sum_{k=1}^{j-1} dp_{i-1, k} &(s_{i-1} = '<') \\ &\sum_{k=j}^{i-1} dp_{i-1, k} &(s_{i-1} = '>') \end{aligned} \right.$$

直接用这个鬼玩意的复杂度是 的，过不了此题。

于是考虑优化：这道题的优化是最简单的。直接前缀和优化即可。时间复杂度 。

三倍 EXP：UVA1650 Number String，P2467 地精部落

AT_dp_u Grouping

这道题可以想到一个非常简单的 dp：假设 代表只考虑 这个集合的最大贡献。于是列式子：

$$val_{S\cup T} = \max_{S \cap T \neq \emptyset}(val_{S\cup T}, val_{S} + val_{T})$$

（初始设 为把 集合整体分为一组所得的值。）

但是不好枚举，然后转化一下：

$$val_{S} = \max_{T \subseteq S}(val_{S}, val_{T} + val_{\complement_S T})$$

这样是好枚举的。

直接用这个鬼玩意的理论复杂度是初始化 和 DP 复杂度 的，但是过得了此题（可能是因为 ATCoder 机子非常的强大）。

但是运行了 1.3s，还是要考虑优化：这个 DP 非常浪费的一个地方就是枚举了非常多的不包含于 的 。那么怎么才能枚举所有的 让它们都属于 呢？

有一个方法：因为这里的集合使用一个二进制数表示的，所以可以先从 开始枚举，然后下一个是 (T-1) & S。这种方法可以完美的枚举所有 的子集。

时间复杂度预处理 ，DP 。

证明枚举子集的复杂度为 的博客：枚举子集为什么是 O(3^n) 的 - yspm - 博客园

AT_dp_v Subtree

这道题就是在树上做 dp。（感觉说了和没说一样

因为这是一棵无根树，所以就先钦定节点 1 为根。然后设状态。又因为是在强制把这个节点染成黑色的情况，所以连通要么黑色点连在下面，要么连在上面。而因为遍历一棵树最常用的方法是 DFS，所以我们把 dp 状态分成两个：

1. ：设其为当黑色点全在以 为根的子树内（包含点 ）的方案数。
2. ：设其为当黑色点全在以 为根的子树外（也包含点 ）的方案数。

然后总答案就是 了。

那我们该如何求呢？首先，对于 ，它的答案是根据它的儿子决定的。很容易得出：。而这个 就是当儿子 取白色的情况，其他就是儿子 取黑色的情况。这就相当于是，它有它的儿子的个数种选择，然后求方案数。而当 为叶子节点时，很明显，。

而对于 ，因为它要和不是它的子树的点连通，所以肯定就要经过它的父亲。那么就相当于是变为了它的直系兄弟的 之积。而又因为 是向外面连通的，父亲的祖先也不例外，所以还要多一个选择，即再乘上 。最后再加上 ，表示只选 点，不选 及其他点。而当 为根时，明显的、。

AT_dp_x Tower

我们可以想到一个朴素的算法：先定一个 数组， 表示目前箱子总重量 所可以获得的最大价值。假如说新加了一个箱子 ，那么我们可以将 全部更新一遍。（要反序因为是背包）最后求最大值。因为 ，，所以时间复杂度就算是 或 也可以接受。

但是遇到了一个问题：如何确定放箱子的顺序使最终答案最优？

不容易想到（我看了 tj），现在有两个箱子 ，让 在 前面使这样更优的情况可以做如下解释：现在你假定 和 都要选，那么如何安排顺序使最终答案更优？那就分两种情况讨论：

• 若 在 上面，那么还可以放 的重量在 上。
• 若 在 上面，那么还可以放 的重量在 上。

这样就好理解了，哪个的剩余重量大就选哪种情况。所以将 优先于 的情况则当：

$$s_y - w_x \le s_x - w_y$$

于是在开头的 init 部分排序排一下优先级，就做出来了。

AT_dp_z Frog 3

董晓算法：E51【模板】斜率优化DP 打印文章_bilibili