本文为 @A_zjzj《dp 专题》学习笔记。
转移性质
Lanterns
题意：\(n\) 个灯笼拍成一排，第 \(i\) 个灯笼具有 \(p_i\) 的亮度。每个灯笼要么朝向左照亮 \([i - p_i, i - 1]\)，要么朝向右照亮 \([i + 1, i + p_i]\)。
寻找一种方案，为所有的灯笼定向，使得每一个灯笼被至少一个其他灯笼照亮。\(2 \le n \le 3\times 10^5, p_i \in [0, n]\)。
设 \(f_i\) 表示前 \(i\) 盏灯能覆盖的最长前缀，考虑几种转移：
- 前 \(i - 1\) 盏灯能覆盖 \(i\)，\(f_i \gets \max(f_{i - 1}, i + p_i)\)。
- 前 \(i - 1\) 盏灯不能覆盖 \(i\)，先把 \(i\) 忽略，之后再定向，\(f_i \gets f_{i - 1}\)。
- \(i\) 向左覆盖，存在一个 \(f_j + 1 \ge i - p_i\)，所有 \((j, i)\) 的灯向右定向，\(f_i \gets \max(i - 1,\ j + 1 + p_{j + 1}, \cdots, i - 1 + p_{i - 1})\)。
显然有 \(f_{i - 1} \le f_i\)，二分 \(j\)，树状数组维护后缀最大值。submission
来源不明的一道题
题意：给出 \(n\) 和 \(a_{2 \sim n}, b_{2 \sim n}\)，表示 \(i\) 有单向边连向 \([a_i, i - 1]\)，\([b_i, i - 1]\) 有单向边连向 \(i\)，边权为 \(1\)。
设 \(d(i, j)\) 表示 \(i\) 到 \(j\) 的最短路，求 \(\bigoplus_{i, j} d(i,j) \times (i + j)\)。\(1\le n\le 6000,\ a_i < i,\ b_i < i,\ \text{1s}\)。
如果从 \(i\) 向左走一步到 \(j\)，紧跟着向右走到 \(k\)，这是一定不优的：
- \(k \le i\)，显然有 \(a_i \le j < k \le i\)，可以一步或零步走到。
- \(k > i\)，\(j\) 能一步到 \(k\)，说明 \(b_k \le j\)，说明 \(i\) 也能一步到 \(k\)。
因此最优方案一定是先向右走若干步，再向左走若干步。
枚举起点 \(s\)，设 \(f_i\) 表示 \(s\) 到 \(i\) 的最短路，分两部分转移（从前往后扫一遍，再从后往前扫一遍）：
第一部分：\(f_i \gets f_j + 1,\ b_i \le j < i\)；第二部分：\(f_i \gets f_j + 1,\ a_j \le i < j\)。可以线段树做到平方对数。
以向右的转移为例，如果 \(i < j\land f_i \ge f_j\)，\(f_i\) 显然不优。
设 \(g_x = \max_\limits{j < i\land f_j = x} j\)，表示值为 \(x\) 时的最优决策点，显然 \(f_i\) 的上界为 \(x = f_{i - 1} + 1\)。不断使 \(x \to x - 1\)，直到 \(g_{x - 1} < b_i\)。
用 \(x\) 更新 \(f_i\)，并使 \(g_x = i\)。上述做法依赖于 \(g_0\sim g_{f_{i - 1}}\) 是单调递减的，可以归纳证明。势能增量 \(O(n)\)，复杂度 \(O(n)\)。
对于向左的转移，如果 \(a_i \le a_j \land f_i \le f_j\)，\(f_j\) 显然不优。设 \(g_x = \min\limits_{j > i \land f_j = x} a_j\)。
\(f_i\) 的上界是 \(\min(f_i, f_{i + 1} + 1)\)，不断使 \(x \to x - 1\)，直到 \(g_{x - 1} > i\)，归纳证明 \(g_0 \sim g_{f_{i + 1}}\) 是单调递增的。
时间复杂度 \(O(n^2)\)。submission
一类特殊题型
求一个排列 \(\{p\}\)，最小（大）化如下值：
\[\sum_{i = 1}^{n - 1} f(p_i, p_{i + 1}) \]其中 \(f(i, j)\) 如下：
\[\begin{cases} a(i) + b(j) & i > j\\ \\ c(i) + d(j) & i < j \end{cases} \]考虑按照 \(p_i\) 的大小，从小到大插入序列的过程，维护若干连续段（只是说明某些元素在最终排列上连续，并没有确定位置）。
每次插入有以下情况：
- 将两个连续段合并成一个。
- 插入一个连续段的左边/右边。
- 新增一个连续段。
由于保证了插入顺序，容易算出每个元素的贡献。另外，需要维护连续段个数，保证最终连续段合并成一个。
可能需要判断插入时是否插在全局的开头或末尾。
Ant Man
题意：给定排列 \(\{p\}\) 的第一个元素 \(s\) 和最后一个元素 \(e\)，找出一个排列，最小化：
\[\sum_{i = 1}^{n - 1} \begin{cases} \vert x_i - x_{i + 1}\vert + c_i + b_{i + 1} & p_{i + 1} < p_i\\ \\ \vert x_{i + 1} - x_i\vert + d_i + a_{i + 1} & p_{i + 1} > p_i\\ \end{cases} \]其中，\(2\le n \le 5000,\ x_1 < x_{2} < \cdots < x_n\)。
和原模型基本一致，\(f(i, j)\) 表示插入前 \(i\) 个数，分成 \(j\) 个连续段的最小代价。
注意 \(s, e\) 没有合并连续段的转移，\(s\) 只算右边贡献，\(e\) 只算左边贡献，\(s\) 所在连通块不能右插，\(e\) 不能左插。
新增一个 \(i\) 作为连通块时，需要满足 \(j - [i > s] - [i > e] \ge 1\)，否则无法新增。submission