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

三维偏序实际上就是经典题目 —— 逆序对 的升级版。但是前者是三维，而后者只是一维（啥比了，逆序对是二维的）。

我们可以利用一些技巧压掉第一维度，即：将这些元素按主键元素排序，于是，对于所有的 $i \lt j$，都有 $a_i \le a_j$，于是第一维被压掉了。

接下来我们考虑怎么压掉第二维，以转化到我们熟悉的逆序对。这里要用到 CDQ 分治。

CDQ 分治适用于区间上的一些操作：通过将大区间上的操作分割成小操作并归纳，我们可以免去处理合并的问题，只考虑对区间进行统计。

例如此题中，我们在分治过程中得到了两个子区间，现在我们要做的就是统计这两个子区间之间的三维偏序数量。

不妨将两个区间排序，设为 $L$ 与 $R$，那么对于所有 $0 \le i, j \le T$，都有 $a(L_i) \le a(R_j)$（因为 $i$ 和 $j$ 在原序列中是增的）。我们接下来要找的是满足 $b_i \le b_j$ 且 $c_i \le c_j$ 的。用一个双指针即可。

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

数位 DP 的状态模板是设 $f(i, j)$ 表示第 $i$ 位，限制为 $j$ 时的方案数量。其中，$j = 1$ 表示有限制，即这一位上最大为 $x_i$；否则，这一位上最大为 9。

本题在简单数位 DP 的基础上，还加了一个条件：两数相差至少为 2。

这时候，朴素状态显然无法保证这一条件。那么我们加一维度，设 $f(i, j, k)$ 表示第 $i$ 位，限制为 $j$，且这一位为 $k$ 时候的方案数量。那么我们就能得出一个明显的转移，懒得 $\LaTeX$ 了。

但是有一个问题：考虑前导零。如果我们就用上面的方式转移的话，很明显这会出错，因为 1 不会被考虑在内。这时候，我们可以手动处理一下特殊情况：将前导零的情况特判，然后再转移即可。

btw 数位 DP 这种东西好恶心）

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

我们注意到一个重要的性质：每一行每一列最多只能放两个炮。

我们可以设 $f(i, j, k)$ 表示已经放完前 $i$ 行，$j$ 列是空的，$k$ 列放了一个，那么有 $m - j - k$ 列放了两个。我们并不需要知道具体是哪一列放了一个两个或者零个，只需要统计方案。

转移（这里滥用 $\gets$ 表示在原来的值上加）：

• 不动，转移到下一行：$f(i, j, k) = f(i-1, j, k)$

• 放一个，分成放到一个原来空着的列：$f(i, j, k) \gets (j+1)\cdot f(i - 1, j + 1, k - 1)$

• 放到一个原来有一个的列：$f(i, j, k) \gets (k + 1)\cdot f(i - 1, j, k + 1)$。

• 放两个，又分成两个都放到原来空着的：$f(i, j, k) \gets \dfrac12 (j + 2)(j+1)\cdot f(i - 1, j + 2, k - 2)$

• 一个放到空着的，另一个放到原来有一个的：$f(i, j, k) \gets (k + 1)(j + 1)\cdot f(i - 1, j + 1, k + 1)$

• 都原来有一个的：$f(i, j, k) \gets \dfrac12\times (k+2)(k + 1) \cdot f(i - 1, j, k + 2)$

然后转移。

本文章由 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 充分利用了树状结构的天生的最优子结构性质，是十分优雅的。

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