本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-05 19:55:53

我们先考虑怎么求解边权都为一的情况。题目中给我们的是一个邻接矩阵。我们设 $f(i, j)$ 表示从点 $1$ 走到点 $i$，走 $j$ 步的方案数量，那么显然有：

$$f(i, j) = \sum\limits_{k=0}^n M_{ki} \times f(k, j - 1)$$

换一个角度，如果将 $f(i,j)$ 看作是矩阵（向量） $f$，那么有：

$$f_{ij} =\sum\limits_{k=0}^n M_{ki} \times f_{kj-1}$$

我们滥用一下符号，于是后面实际上是个矩阵乘法 $f_{j-1}\times M$。我们就有：

$f(i, j) = f(i,j-1)\times M$。

我们要求的是 $f(i, t)$，展开一下就是 $M^t$。由于 $M$ 是方阵，我们可以用矩阵快速幂。

然后我们来考虑本题：虽然有了边权，但实际上边权最大也只是 $9$，那么我们可以这么考虑：建一些虚点设为 $\sigma_{ik}$，这些虚点之间的边权都是一，然后就转化成了上一个问题。

btw，发现矩阵乘法用循环展开可以卡两倍常

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-06 16:28:22

$\sum\limits_{i=1}^n a_ix_i=b$，我们注意到：不等式只能有零个或者无穷多个解。因为若 $b$ 可以使不等式有解，那么我们可以构造出 $b + a_k$，其中 $a_0$ 是 $a$ 的任意一个元素。我们有：

$$a_k\cdot (x_i+1) + \sum\limits_{i=1, i \neq k}^na_ix_i=b+a_k$$

实际上，我们并不需要考虑每一个 $b$，只需要考虑其在 $\mod a_k$ 意义下的情况。因为对于所有 $b \gt a_k$，我们都可以设 $b' = b - a_k$，此时有：

$$a_k\cdot (x_i-1) + \sum\limits_{i=1,i\neq k}^n a_ix_i = b - a_k$$

即，若有 $b \ge a_k$ 可以满足这个不等式，一定可以找到 $b' \in \mod a_k$ 满足这个不等式。

于是我们设 $f(x)$ 代表在 $[x]$ 内满足此不等式的最小值，那么 $f(x) = \min\limits_{i=0}^n f(x - a_i) + a_i$。这和最短路的松弛操作很像。于是我们可以用最短路来做。

求出所有的 $f(x)$ 后，统计根的数量即可。

不得不说这题作为紫的确有点水了，说不定以后会和数位 DP 一样降绿（）

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-27 19:46:13

动态规划的思路就是保存先前的计算结果，以减少后续问题的计算量。这在另一个维度上看，就是保存子问题的解，并以此构造原问题的解。

动态规划能将高复杂度的搜索等算法，转换为多项式复杂度的较优算法，非常强大，但它也有优化的空间。

在本篇文章中我们将介绍一些简单的动态规划问题的优化，以此介绍较难一些动态规划问题的优化思路。

斜率优化

这样的状态转移方程可以考虑斜率优化：

$$ \begin{aligned} f(i) = \min\limits_{j \le R_i} \{f(j) + A_i\times B_j\} ,\space \text{s.t.} \space R_t \le R_{t + 1},A_t \le A_{t+1}, B_t \le B_{t+1} \end{aligned} $$ （$\min$ 也可为 $\max$）

这样的方程一般来说是 $O(n^2)$ 的，在优化后可以达到 $O(n)$。下面是推导过程。

我们先将 $i$ 及关于 $i$ 的所有函数看作常量，同时去掉最值限制，做一点变形得到

$$ g(j) = A_i\times j - f(i) $$

（请思考：若 $B$ 并不递增，匆忙抽象出 $g$ 会导致什么问题？）

那么，在 $[0, R_i]$ 里，我们有一系列直线，记作 $g_1, \cdots, g_t$，它们的斜率均为 $A_i$，即它们互相平行。

我们回到问题：我们要求的是 $f(j) + A_i\times B_j$ 最小，实际上在将 $i$ 看为静止后，问题变成了求 $g_1, \cdots, g_t$ 中截距最小的直线所对应的自变量。

我们将每一个 $j \le R_i$ 入队进行处理。我们有如下性质：

斜率优化原理 设 $k_{ij}$ 表示 $g(i)$ 与 $g(j)$ 连线的斜率。我们有：对当前入队的点 $t$，若有 $x \lt t$ 使得 $k_{x+1,t} \lt k_{x, x+1}$，那么我们有 $b_{x+1}$ 至少大于 $b_t$ 与 $b_{x}$ 中的一个。也即，$x + 1$ 一定不是这三点中的最小值。

这个性质可以帮助我们排除队中的非最优点。以下对 $x = t - 1$ 时的证明：

$$ \begin{aligned} k_{t-2, t-1} - k_{t-1, t} &= \frac{A_i\times ((t-1) - (t-2)) + b_{t-1} - b_{t-2}}{(t-1)-(t-2)} - \frac{A_i\times (t - (t-1)) + b_t - b_{t-1}}{t - (t-1)} \ &= b_{t-1}-b_{t-2}-b_t + b_{t-1} \ &= 2b_{t-1} - b_{t-2} - b_{t} \ge 0 \

\text{i.e.} \space 2b_{t-1} \gt b_{t} + b_{t-2} \end{aligned} $$

反证，容易得到 $b_{t-1}$ 至少大于 $b_t$ 与 $b_{t-2}$ 中的一个，即 $g(t-1) \ne \min \{g(t), g(t-1), g(t-2)\}$

（请自己证明一般情况）

我们继续考虑求每个 $f(i)$ 的问题。我们容易发现：$f(i)$ 是 $[0, R_i]$ 上的最小值。由于 $R$ 是增序列，那么 $[0, R_{i + 1}]$ 一定包含了 $[0, R_i]$。由此，$f(i + 1)$ 一定小于等于 $f(i)$。我们由 $A$ 的单增性可知，处理 $f(i)$ 所得到的所有 $j$ 上的直线，其斜率一定小于 $f(i + 1)$ 上的同类。由此，我们不需要对每一个 $i$ 都维护一个队列，只需要在一个固定的队列上操作即可。

以上是斜率优化。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-28 10:51:42

单调队列适合这样的转移方程：

$$ f(i) = \min\limits_{L_i \le j \le R_i} \{f(j) + a_j\} + b_i \space \text{s.t.} \space L_t \lt L_{t + 1}, R_t \lt R_{t + 1} $$

如果我们使用朴素的方法求解这个方程，时间复杂度大约是 $O(n^2)$ 的（实际上是 $O(\delta n)$，其中 $\delta$ 是每一个区间的宽度）。这是因为对每一个点 $i$，我们都需要遍历一个区间内的 $j$ 并且取其最值。

我们发现，对不同的 $i$，我们计算的 $j$ 是有重叠的；并且，由于这些计算出的结果并不依赖 $i$，因此我们可以使用单调队列的方法，保存重叠的 $j$ 区间中 $f(j) + a_j$ 的最大值。

这样，在计算 $f(i)$ 的时候，我们只需要在单调队列中加入找到在这个区间内的最大值即可。由于这些区间都是递增的，因此超出了某个点 $i$ 的点 $j$，我们可以直接将其从队列中删除。

这样实际复杂度达到 $O(n)$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-01 13:13:40

设 $f(i, j)$ 表示可以建 $j$ 个小学时，给前 $i$ 个村庄建小学的最短距离和，那么状态转移方程：

$$ f(i, j) = \begin{cases} 0 & j > i \ \min\limits_{k = j - 1}^i{f(k, j - 1) + \sigma_{k + 1, i}} & \text{otherwise} \end{cases} $$

这也就是说，给前 $i$ 个村庄建 $j$ 个小学的最小花费，就是从 $j - 1$ 到 $i$ 中选一个 $k$ 作为分割点，在前 $k$ 个村庄里建 $j - 1$ 个小学，然后在 $k + 1$ 到 $i$ 个村庄里建一个小学。

这里面，$\sigma_{i, j}$ 表示在 $i$ 到 $j$ 个村庄中建一个小学的最短距离和，它是一个定值。

那么 $\sigma$ 怎么求呢？在 $[i, j]$ 中，最短距离和一定是在中点处，因为每个村庄的坐标是递增的。我们可以证明，在中点处左移或者右移动，均会使最终的值更大。故中点一定最优。

所以我们就可以求出 $\sigma$ 的值，随后计算方程即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 11:33:09

本题虽然是在树上的操作，但是实际上是区间 DP 的典题。

我们知道：在中序遍历中，一个点左边的序列和右边的序列就是其左子树和右子树。因此，我们的问题就转化为了求区间中的最优分割点 $k$，使 $\sigma_{l,k-1} \times \sigma_{k+1,r} + \sigma_{k,k}$ 最大。

之后的问题就是找到先序遍历。这实际上也是很简单的。我们将每一个区间的最优分割点保存下来，于是这个点就是这个区间所建的树的根。之后打印即可。

总之，对于中序遍历的问题，我们可以转化为区间上的问题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 13:28:09

题意很明确，就是选择虚拟根的 $m$ 个子树使得总和最大。

这也是很经典的背包问题：在每一个子树上，我们做一次背包，得到这个子树在 $0$ 到 $m$ 的体积上的所有最值。然后处理根：很明显，这就是一个零一背包。

树形 DP 充分利用了树状结构的天生的最优子结构性质，是十分优雅的。

虚拟根的技巧也是很优雅的，可以将本来不联通的几棵树转化为一颗。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 18:22:38

典型的树形背包，比如 P2014 选课，其复杂度是 $O(nm^2)$ 的。但实际上，我们可以达到 $O(nm)$ 的优秀复杂度。

常规的做法是：对每一个节点，我们计算它子树在 $0$ 到 $m$ 上的最优值，然后枚举每一个子节点被分配给的空间大小，并求得最值。

我们考虑优化：不将节点看作是树形的，而是将它摊平。对某一个点 $p$ 的子节点 $q$，它的初始值是 $p$ 在当前的值。也就是说，将这个树摊平之后，$p$ 成为第 $i$ 个节点，而它的孩子 $q$ 是第 $i + d$ 个，我们有 $f(i+d)_0 = f(i)$。

在转移时，我们不需要考虑“给某个子节点分配多大的空间”，因为它们此时都是并列的。在总空间为 $t$ 时，给这个孩子的便是 $t - 1$。

于是最后的复杂度就是 $O(nm)$ 的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 10:55:51

我觉得是一道比较好的思维题。

当只有 $m$ 个荷叶的时候，明显我们最多有 $m + 1$ 个青蛙。从 $A$ 出发依次跳到 $m$ 个荷叶上，最后一只青蛙直接跳到 $D$，然后再顺次跳到 $D$ 上即可。

我们看石墩。石墩增加一个，可以过的青蛙翻倍。很简单，我们设原来有 $m$ 个荷叶，那么最多能过 $m + 1$ 个青蛙。增加石墩后，我们让前 $m$ 个青蛙跳到荷叶上，第 $m + 1$ 个跳到石墩上，然后让这 $m$ 个再跳到那个石墩上，现在这个石墩上就有了 $m + 1$ 只青蛙。之后我们按照原来的方法转移即可。

于是最终的答案就是：$(m + 1) \times 2^n$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-07 08:52:18

赛时 24 分切了 ABC，看了 D 感觉很恶心就没做，就做开了 E。最开始还以为是个简单的 DP，结果越做越不对劲，有几个坑点：

• 求的是路径的长度，不是权值和
• 求的路径长度要求权值要去重
• 更要命的是，没去重之前路径的最长值不是去重后的最长值

所以一直卡到 9:39 分还在调一个基于集合的屎山 DFS + DP。后来看了一篇题解豁然开朗。

我们可以将权值相同的节点视作一个节点，然后建小权值指大权值的有向图，之后用拓扑求最长路即可。

但是它扛不住这个 hack

4 4
1 2 1 4
1 2 2 3 2 4 3 4

我们的代码输出 0，因为这时点 2 的入度是 2（1 和 3），而 3 是永远访问不到的，故我们就访问不到 4。我们需要改一下，只建能从 1 能访问到的边，即跑一边 DFS 记录，然后重新建边即可。