然而我 dp 废的一比（梅开二度）
优化 dp
作为 dp 废物，这里记录一下（反正我不会的） dp 优化方法
dp 的关键有：状态、初始化、转移、循环
倍增优化
倍增是一种很优美的思想，大部分动态规划的都是采用阶段的线性增长，而在有些题中，可以考虑倍增增长（类似 ST 表的预处理），而这种优化常常会把 $2^k$ 中的 $k$ 记入状态中，类似区间 dp ，关于 $k$ 的循环往往在外层
而倍增优化的 dp 往往是这类问题的第一部分（也是最难的部分），通过 dp 我们得到若干与 $2$ 的整次幂相关的状态；在第二部分，我们会用这些状态“拼凑”（一般基于二进制拆分）出最后答案
例一
题意
给定 $n \le 10^5$ 个不同的数 $\mid h_i \mid \le 10^9$ ，记 $dis(i, j) = \mid h_i - h_j \mid$ ，两种操作轮流进行，设当前在 $i$ ，第一种会找到满足 $j > i$ 且使 $dis(i, j)$ 取次小值（相等则认为 $h_j$ 小的小，下同）的 $j$ ，并以 $dis(i, j)$ 的代价到达 $j$ ；第二种会找到满足 $j > i$ 且使 $dis(i, j)$ 取最小值的 $j$ ，并以 $dis(i, j)$ 的代价到达 $j$ ，但无论如何，总代价不能大于 $X \le 10^9$ ，当操作无法进行下去时就结束，现在有两个问题：
- 对于给定的 $X= X_0$ ，求从那个数出发，操作一耗费的代价与操作二耗费的代价比值最小，若有多个答案，输出 $h_i$ 最大的
- 给出 $m \le 10^5$ 次询问，每次给定 $X = X_i$ 和出发点 $st_i$ ，分别求两种操作耗费的代价
思路
首先预处理出从每个 $i$ 出发，两种操作会到达的点，记为 $g[0/1, i]$ ，用一个 set 倒序扫描即可
本题信息有三个：位置、操作次数、代价，如果直接以其为状态，复杂度过高，注意到操作是轮流进行的，考虑倍增优化，设 $d[0/1, i, j, 0/1]$ 表示“对于操作一/二，从 $j$ 出发先做操作一/二，操作 $2^i$ 次后的代价”，初始化和转移比较明显：
$$
\begin{aligned}
& & d[0, 0, j, 0] = dis(j, g[0, i]), d[0, 0, j, 1] = 0 \\
& if (i = 1) & d[0, 1, j, k] = d[0, 0, j, k] + d[0, 0, x, k \oplus 1] \\
& else & d[0, i, j, k] = d[0, i - 1, j, k] + d[0, i - 1, x, k] \\
\end{aligned}
$$
这里一定要单独考虑 $i = 1$ 的情况，因为只有 $2^0 = 1$ 是奇数， $d[1]$ 类似
不难发现状态数是 $O(2 * \log n * n * 2) = O(4 n \log n)$ （这里先把常数留一下），所以留给转移的时间最多是 $O(\log n)$ ，而转移的关键在于上面方程中的 $x$ ，它的含义是“前面那步走到的城市”，如在 $i \ne 1$ 时， $x$ 指“从 $j$ 出发先做操作 $k$ ，进行 $2^{i - 1}$ 次操作到达的城市”，这个东西可以 dp 预处理，具体地，设 f[i, j, 0/1] 表示“从 $j$ 出发先做操作一/二，进行 $2^{i}$ 次操作到达的城市”，初始化和转移如下：
$$
\begin{aligned}
& & f[0, j, 0] = g[0, j], f[0, j, 1] = g[1, j] \\
& if (i = 1) & f[1, j, k] = f[0, f[0, j, k], k \oplus 1] \\
& else & f[i, j, k] = f[i - 1, f[i - 1, j, k], k] \\
\end{aligned}
$$
预处理时间明显 $O(n \log n)$ ，然后 $d$ 的转移可以做到 $O(1)$
于是我们在 $O(n \log n)$ 的时间内完成了计算所有操作次数为 $2^i$ 形式的信息，现在，对于问题二，类似 lca 倒序枚举 $i$ 移动即可，时间为 $O(\log n)$ ，而对于问题一，直接枚举起点转化成问题二即可，故总的时间为 $O(n \log n + 4 n \log n + n \log n + m \log n) = O(n \log n)$ 常数在 $10$ 左右，完全可以过
代码
马蜂毒牛（ dp 码风重拳出击，数据结构唯唯诺诺）
1 |
|
例二
题意
多组数据，定义 conn(s, n) 为 $n$ 个字符串 $s$ 形成的字符串，如 conn("abc", 2) = "abcabc" ，每次给定长度 $\le 100$ 的字符串 $s_1, s_2$ 和两个整数 $n_1, n_2 \le 10^6$ ，求一个最大的 $m$ 使得 $conn(conn(s_2, n_2), m)$ 为 $conn(s_1, n_1)$ 的子串
思路
首先， $conn(conn(s_2, n_2), m) = conn(s_2, n_2 * m)$ ，现在问题转化为求 $m’ = n_2 * m$
注意到 $m’ \le N = \frac{\mid s_1 \mid * n_1}{\mid s_2 \mid}$ ，而 $N \le 10^8$ 过大，不好直接枚举，考虑将 $m’$ 二进制拆分，设 $m’ = 2^{p_0} + 2^{p_1} + … + 2^{p_{t - 1}}$ ，则 $conn(s_2, m’)$ 可看作 $conn(s_2, 2^{p_0}), conn(s_2, 2^{p_1}), …, conn(s_2, 2^{p_{t - 1}})$ 着 $t$ 个串首尾衔接得到，考虑对于每个 $k \in [0, \log N]$ ，求出 $conn(s_1, n_1)$ 从每个位置开始，最少要多少个字符才能和 $conn(s_2, 2^{k})$ 匹配上（就是含有该子串），这样我们就又可以用类似 lca 的方法拼凑出答案，但 $cons(s_1, n_1)$ 也很长，不妨当成 $conn(s_1, \infty)$ ，但只算从 $s_1$ 的各个位置开始的情况
综上，定义 d[i, j] 表示“从 $s_1[i]$ 开始，至少要多少个字符，才能匹配 $conn(s_2, 2^j)$ ”，则转移方程为：
$$
d[i, j] = d[i, j - 1] + d[(i + d[i, j - 1]) \mod \mid s_1 \mid, j - 1]
$$
初始化 $d[i, 0]$ 可以暴力计算， dp 的总时间复杂度为 $O(\mid s_1 \mid \log N)$
然后用得到的状态拼凑答案，类似于 lca ，具体见代码
代码
要注意的地方是：
-
d要开long long - 第 $18$ 行是
x + 1，因为我下标从 $1$ 开始的 - 本题输入非常毒瘤，如果用
cin一点问题没有，但如果用scanf因为数据最后有个换行所以会 TLE ，不过可以利用scanf返回值解决
1 |
|
数据结构优化
对于大部分 dp 高效的转移非常重要，通过选取适当的数据结构，可以大大提高 dp 效率
这类问题的难点一般不在数据结构上，它仅仅做一个辅助转移的工具，关于工具的选取还要看题目本身的性质
当然有时候我们会需要在数据结构上 dp ，这种情况本质上并不是优化 dp 这里就不再做讨论
例题三
还是看到题： 赤壁之战
题意
给定长度为 $n \le 1000$ 的序列 $a_i$ ，求 $a_i$ 有多少个长度为 $m$ 严格递增子序列，多组数据，答案对 $10^9 + 7$ 取模
思路
dp 方程一眼就出来： d[i, j] 表示以 $j$ 结尾的长度为 $i$ 的严格递增子序列的个数，有 $d[i, j] \gets d[i - 1, k] (k < j \wedge a_k < a_j)$
仔细一看， $n \le 10^7$ ，直接 dp 是 $O(n^2m)$ 的，这不完蛋，但，先打出来看看
1 | d[0][0] = 1; |
在枚举 $j, k$ 时，可以把最外层的 $i$ 当作定值不管，发现当 $j$ 加 $1$ 后， $k$ 的范围也仅变化了 $1$ ，但决策是变化了不知道多少的，因为条件 a[k] < a[j] 中的 a[j] 变了，考虑用树状数组，把 $a_i$ 离散化，每次查询前缀和并插入一个数，于是第三层循环的 $n$ 变成 $\log n$ ，总时间为 $O(m n \log n)$
代码
1 |
|
单调队列优化
从这里开始是对于转移的优化
在 dp 中，我们常常遇到这种方程（有时候不尽相同，但通过把外层变量当定值等方法可以化成这样）：
$$
d[i] = \min_{l(i) \le j \le r(i)} (d[j] + val(i, j))
$$
其中 $\min$ 可换成 $\max$ ， $val(i, j)$ 是关于 $i, j$ 的多项式函数（通常它是决定优化方式的关键）， $l(i), r(i)$ 限制了 $j$ 的决策范围且保证上下界变化具有单调性，上述问题被称作 1D/1D 动态规划，因为它的状态和转移都是 $O(n)$ 的
如果上面方程中，满足 $val(i, j)$ 中的每一项仅与 $i, j$ 中一个有关，我们就可以考虑把关于 $i, j$ 的项分开，对于关于 $i$ 的部分，它与 $j$ 无关，可以每次跟新 $i$ 后再计算；对于关于 $j$ 的部分，由于 $l(i), r(i)$ 的单调性，可以用单调队列优化
例题四
题意
给定长度为 $n \le 10^5$ 的序列 $0 \le a_i \le 10^6$ ，要求把序列分成若干段，在满足“每段的和不超过 $m \le 10^{11}$ ”的前提下，让“每段的最大值之和”最小，求最小值
思路
照着题意设方程，定义 d[i] 表示“把前 $i$ 个数分成若干段，在保证每段和不超过 $m$ 的前提下，每段最大值之和的最小值”，转移方程：
$$
d[i] = \min_{0 \le j < i \wedge \sum_{k = j + 1}^i a_k \le m} (d[j] + \max_{j + 1 \le k \le i} (a_k))
$$
直接转移明显 $O(n^2)$ ，并且 $val(i, j) = \max_{j + 1 \le k \le i} (a_k)$ 似乎很难用多项式表示，思考转移优化的指导思想：及时排除不可能的决策，保持候选决策集合的秩序性和有效性，我们来看看何时决策 $j$ 是必要的
引理：
决策 $j(0 \le j < i \wedge \sum_{k = j + 1}^i a_k \le m)$ 是最优策略的必要条件是它至少满足下面两个式子之一：
- $a_j = \max_{j \le k \le i} (a_k)$
- $\sum_{k = j}^i a_k > m$ 或者说 $j$ 是最小的满足 $\sum_{k = j + 1}^i a_k \le m$ 的数
证明：
设 $j$ 两个条件都不满足，则由条件 $1$ 有 $\max_{j \le k \le i} (a_k) = \max_{j + 1 \le k \le i} (a_k)$ ，再由条件 $2$ 可知决策 $j - 1$ 合法，又因为明显 $d[j - 1] \le d[j]$ ，有 $d[j - 1] + \max_{j \le k \le i} (a_k) \le d[j] + \max_{j + 1 \le k \le i} (a_k)$ ，即决策 $j - 1$ 优于决策 $j$
QED
那么，现在来看看引理如何指导 dp ，首先是条件 $2$ ，可以直接对每个 $i$ 预处理出最小的 $j$ ，然后直接进行一次转移即可（然而后面会有更简单的实现方法）；而对于条件 $1$ ，考虑优先队列，当一个新决策 $k$ 入队时，若队尾决策 $j$ 满足 $j < k (这个条件显然) \wedge a_j \le a_k$ 那么 $j$ 一定不优于 $k$ ，这样看来只要维护一个 $a_i$ 单调递减的队列，就可以做到 $O(n)$ 的 dp 了……吗？
发现我们只能保证队列中的元素可能为最优决策，但队头不一定是令 $d[j] + \max_{j + 1 \le k \le i} (a_k)$ 取得最小值的 $j$ ，如果直接扫描队列时间又变回 $O(n^2)$ 了，故我们要快速找到队列中的最优解，考虑数据结构，它要支持查询最小、插入、删除——这不平衡树吗（好像二叉堆 + 懒惰删除也行）？直接维护一个内部元素于单调队列相同的平衡树即可，总时间 $O(n \log n)$
最后一个小问题： $\max_{j + 1 \le k \le i} (a_k)$ 可以用 ST 表做到 $O(1)$ ，但其实仔细思考可以发现，队列中某一项的 $\max_{j + 1 \le k \le i} (a_k)$ 就是它下一项的 $a_i$
代码
- 特判无解的情况
- 关于条件 $2$ 的实现，可以不必预处理，记录一个当前 $sum$ 和对应最小的 $j$ ，即 $L$ 当队列中只有一个元素时就用 $L$ 转移，同时 $L$ 还可以帮助维护队头
- 虽然队列中某一项的 $\max_{j + 1 \le k \le i} (a_k)$ 就是它下一项的 $a_i$ ，但我们的队列（同时对应平衡树）维护的是 $a_i$ ，所以应该是从当前项找到上一项的 $d$ （具体见代码的
calc()函数），而排除/调用最优时要的是 $d$ ，所以要减 $1$ - 本题一定要先插入再转移，原因同 $3$ ，我们维护的是 $a$ ，而转移时调用的是 $d$ ，它可能刚好是当然插入 $a$ 的前一个（另，关于队列的写法，这边建议都写成先插入再转移的）
- 如果你实在觉得这细节来细节去的太麻烦，可以考虑用预处理的方式实现条件 $2$ ，并明确下标，就不必管 $2 \sim 4$ 了（
但代码会变长）
1 |
|
例题五
下面来看一个经典问题，多重背包问题：旅行商的背包
题意
给定 $n \le 10^4$ 种物品，每种物品有 $d_i \le 1000$ 个，体积为 $v_i \le 1000$ ，价值为 $w_i \le 1000$ ，又给定 $m \le 5$ 个特殊物品，第 $i$ 个特殊物品的价值 $y_i$ 与取走的体积 $x_i$ 满足 $y_i = a_i x_i^2 + b_i x_i + c_i$ ，其中 $\mid a_i, b_i, c_i \mid \le 1000$ ，现有一个容量为 $c \le 10^4$ 的背包，求最大价值
思路
由于 $m \le 5$ 很小，可以完全背包暴力做，问题就转化为多重背包的板子，用二进制拆分法的时间复杂度为 $O(n c \log d )$ 可过，但卡的有点死，实际上，用单调队列可以优化到 $O(nc)$
先考虑原来的朴素方程： f[j] （题目已经有 $d$ 了，这里就用 $f$ ）表示“从前 $i$ 个物品中选体积和为 $j$ 的物品的最大价值”（ $i$ 那一维被倒序循环压缩掉了），在转移时，考虑第 $i$ 个物品选了 $cnt$ 个：
$$
f[j] = \max_{1 \le cnt \le d_i} (f[j - cnt * v_i] + cnt * w_i)
$$
考虑状态 $j$ （注意 $j$ 是状态， $cnt$ 才是决策），它的决策集合就是 $\{j - cnt * v_i \mid 1 \le cnt \le d_i \}$ ，不难发现这个集合相比状态 $j - v_i$ 的决策集合 $\{j - v_i - cnt * v_i \mid 1 \le cnt \le d_i \}$ 只变化了一个数，这启发我们把 $j$ 按照 $\mod v_i$ 的余数分组
为了简单，我们完全不必枚举 $j$ ，改为枚举余数 $u \in [0, v_i)$ ，再枚举（这里就正序了） $p = 0 \sim \lfloor \frac{c - u}{v_i} \rfloor$ ，这样就可以计算出 $j = u + p * v_i$ ，故 $j$ 的决策集合就是 $\{u + k * p_i \mid p - d_i \le k \le p - 1 \}$ ，于是方程变为：
$$
f[u + p * v_i] = \max_{p - d_i \le k \le p - 1} (f[u + k * v_i] + (p - k) * w_i)
$$
这里的 $val(p, k) = (p - k) * w_i$ 明显可以分成两部分 $p * w_i$ 和 $-k * w_i$ ，且当 $p$ 减 $1$ 时，上下界 $p - d_i, p - 1$ 都单调变化，这就是典型的单调队列优化模型，我们建立一个决策点 $k$ 递减， $f[u + k * v_i] - k * w_i$ 递减的单调队列，每次取队头跟新即可，时间复杂度 $O(nc)$
代码
本题卡常，吸氧或者加快读可过（我懒就吸氧了）
1 |
|
待续
没想到这么长，打算分成三篇写，会挂链接的