【DP】Educational DP Contest
这份 dp 题单的最后几题好难 orz。
前面的题比较简单，所以我会选取一些题来讲，其它的直接看代码理解吧 qwq。
传送门：
全部 AC 代码：
//atcoder.jp/contests/dp/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi
E
这道题不同于常规的背包问题，因为背包容量很大，我们不能对容量进行 dp，但注意到全部的收益加起来不超过 \(10^5\)，想到用 \(f(j)\) 表示收益至少为 \(j\) 时的最小容量花费。记当前在第 \(i\) 个物品，有状态转移方程：
\]
J
注意到每碟寿司数量最多 \(3\) 个，不难想到用 \(f(x, y, z)\) 表示当前有 \(x\) 盘寿司数量为 \(3\)，\(y\) 盘寿司数量为 \(2\)，\(z\) 盘寿司数量为 \(1\) 时距离吃完全部寿司的期望步数。
根据全期望公式，我们有：
\]
根据上述公式进行记忆化搜索即可，细节见代码。
L
注意到 \(X + Y = sum\)（\(sum\) 是总分数），\(X – Y = 2X – sum\)，所以 Taro 的目标是最大化 \(X\)，Jiro 的目标是最小化 \(X\)。
\(dp(l, r, op)\) 表示 \([l, r]\) 区间轮到某玩家（\(op = 1\) 表示轮到 Taro，否则表示轮到 Jiro）决策时 Taro 的最高得分。
当 \(op = 1\) 时，\(dp(l, r, op) = \max(dp(l+1, r, 0) + w_l, dp(l, r-1, 0)+w_r)\)
当 \(op = 0\) 时，\(dp(l, r, op) = \min(dp(l+1, r, 0), dp(l, r-1, 0))\)
M
\(f(i, j)\) 表示前 \(i\) 个小孩共分了 \(j\) 个蜡烛的方案数，以给第 \(i\) 个小孩多少个蜡烛为状态划分依据。
有方程：\(f(i, j) = \sum_{k = \max(0, j-w_i)} ^ j f(i-1, k)\)
直接转移显然会超时，所以我们在更新 \(f\) 的同时维护一个前缀和 \(s\)，\(s(i, j) = \sum_{k=1}^j f(i, k)\)。
O
\(f(i, st)\) 表示前 \(i\) 个男人和对应子集为 \(st\) 的女人匹配的方案数。
考虑状态转移：
现在已经有 \(i-1\) 个男人以及相应匹配的子集为 \(st\) 的女人集合，当新加入一个男人的时候，对于可以和他配对的女人 \(j\)（而且需要满足这个女人不在 \(st\) 中），我们有状态转移：\((i-1, st)\rightarrow (i,st\cup j)\)。
因此有这样的更新 \(f\) 的方式：\(f(i, st\cup j) += f(i-1, st)\)。
R
倍增 Floyd（是之前没听说过的东西呢）
记 \(g(i, j)\) 为读入的矩阵，\(f(k, i, j)\) 为经过 \(k\) 条边，从 \(i\rightarrow j\) 的方案数。
那么我们有 \(f(k, i, j) = \sum_{u = 1}^n f(k-1, i, u) \times g(u, j)\)
如果看不出有什么性质，那我将上面的柿子换个写法：
\]
注意到，这正是矩阵乘法的形式！也就是：\(f_k = f_{k-1}\times g\)
而且可以发现，\(g\) 恰好为 \(f_1\)，我们有 $$f_k = f_{k-1}\times f_1$$。
所以答案为 \(f_1^K = g^K\)，用矩阵快速幂加速这个过程就好了。
S
数位 dp。
用 \(f(i, j, k)\) 表示区间 \([1, \overline{j99…999}]\) （\(\overline{j99…999}\) 共 \(i\) 位，首位为 \(j\) ），满足十进制意义下数位和 \(mod~D\) 余 \(k\) 的数的个数。
- 对于 \(j = 0\)，\(f(i, j, k) = f(i-1, 9, k)\)
- 对于 \(j\neq 0\)，\(f(i, j, k) = f(i, j-1, k) + [j \equiv k \pmod D] + f(i-1, 9, k-j\pmod D)\)
T
思路比较新颖的 dp。
\(f(i, j)\) 表示对于前 \(i\) 个位置，末位值为 \(j\)，值域为 \([1, i]\) 的合法排列数。
合法就是满足题目中所给的大小关系。
考虑从 \(i-1\rightarrow i\) 的转移、统计：
我们所需要统计的就是 \([1,i]-\{j\}\) 这个值域内有多少个（长度为 \(i-1\) 的）排列是合法的。
如果 \(i-1,i\) 需要满足的关系为 \(<\) ，那么我们有 \(f(i, j) = \sum_{k=1}^{j-1}f(i-1, k)\)，因为在引入 \(j\) 后，原先合法的长为 \(i-1\)，结尾为 \(k\) 的排列在 \([1, i]\) 依然是合法的。
类似地，如果 \(i-1,i\) 需要满足的关系为 \(>\)， 有 \(f(i, j) = \sum_{k=j}^{i-1}f(i-1, k)\)。
一个直观的理解是，当插入 \(j\) 时，\([1, i-1]\) 的每个排列中所有 \(\geq j\) 的数都加了 \(1\)，变换前后的合法方案是一一对应的。
U
\(f(S)\) 表示集合 \(S\) 按在分组后可以得到的最大贡献。
我们不妨记 \(U\) 代表全集，那么答案就是 \(f(U)\)。
以分出一组 \(S\) 的子集 \(S0\) 作为划分依据，有状态转移方程 \(f(S) = \max (f(S-S0) + cal(S0))\)。
\(cal(S0)\) 代表子集 \(S0\) 为同一组时的贡献值。
如果在求取每个状态的时候计算 \(cal\)，那么时间复杂度为 \(O(3^nn^2)\)，无法承受。
所以可以预处理一下所有子集的 \(cal\) 值。
这样做的时间复杂度为 \(O(2^n n^2 + 3^n)\)。
V
换根 dp。
有点恶心的一题。
记点 \(u\) 的合法方案数为 \(f(u)\)，\(u\) 只向子树扩展的合法方案数为 \(f'(u)\)。
对于点 \(u\)，有 \(f(u) = \prod (1 + f'(ch)) \times (1 + \frac{f(fa)}{f'(u)})\)
\(ch\) 代表 \(u\) 的子节点，\(fa\) 代表 \(u\) 的父节点。
因为给出的数不保证存在逆元，因此需要处理出每个点子节点对应的 \(f’\) 值的前缀积和后缀积。
W
个人感觉这道题是这份题单中最难的了 QAQ。
\(f(i)\) 表示前 \(i\) 个位置做出决策后而且第 \(i\) 个决策为 1 所能得到的最大价值。
我们记区间为三元组 \((l, r, v)\)，编号为 \([1, m]\)。
有转移方程：\(f(i) = max(f(j)+\sum v_k)\)，其中 \(k\) 为满足 \(l\in(j,i],r\geq i\) 的区间编号。
我们考虑优化：
对于当前数轴上的位置 \(i\)，假设它处于一个 \([l, r]\) 的区间中，那么我们可以将这个区间的值 \(v\) 加到数轴上的 \([0,l-1]\) 中，那么在统计的时候，只需要统计数轴上 \([0,i-1]\) 的最大值就可以得到 \(f(i)\) 的值了。
位置 \(i\) 处于多个区间的情况类似。
然后我们对数轴上的点 \(i\) 进行更新。
用什么可以高效维护上述数轴上的操作呢？线段树可以做到，也就是区间加以及区间最大值查询。
X
排序 + dp。
考虑从上到下相邻的两个物品 \(i, i+1\) 的属性满足怎么样的关系是最优的排列方式。
所谓最优，就是交换这两个物品的相对位置之后，能够承载上面的物品的重量不比原来的位置好。
也就是 \(\min(s_i, s_{i+1}-w_i)\geq \min(s_{i+1}, s_i-w_{i+1})\)。
下面寻找上式的等价条件：
因为 \(s_i\geq s_i-w_{i+1}\geq \min(s_{i+1}, s_i-w_{i+1})\)，因此上式等价于：\(s_{i+1}-w_i\geq\min(s_{i+1}, s_i-w_{i+1})\)。
类似地，\(s_{i+1}\geq s_{i+1}-w_i\)，故上式进一步等价于：\(s_{i+1}-w_i\geq s_i-w_{i+1}\)，也就是 \(s_i+w_i\leq s_{i+1}+w_{i+1}\)。
至此，我们找到了排序依据。
事实上，直接用 \(\min(s_i, s_{i+1}-w_i)\geq \min(s_{i+1}, s_i-w_{i+1})\) 作为排序依据亦可。
剩下的工作变成背包问题。
记 \(f(i， j)\) 为前 \(i\) 个物品，选取了重量和至多为 \(j\) 的物品的最大收益。
有转移方程：\(f(i, j) = \max (f(i-1, j-w_i)+v_i, f(i-1, j))\)，然后枚举的 \(j\) 的范围是 \([w_i, w_i + s_i]\)。
与背包问题一样，可以减少一维空间。
Y
组合计数 dp。
直接转移有 \(n^2\) 个状态，直接去世。
但是障碍很少，所以可以从障碍入手。
我们记 \(f(x, y)\) 为从 \((1, 1)\) 出发不经过任何一个障碍到达 \((x, y)\) 点的方案数。
那么我们有 \(f(x, y) = C_{x+y-2}^{x-1}f(X, Y)\)，其中 \((X,Y)\) 为障碍点且 \(X<x,Y<y\)。
统计答案和上面的求 \(f(x, y)\) 完全一样，把 \((n, m)\) 看成是障碍点即可。
Z
斜率优化 dp。
记 \(f(i)\) 为跳到 \(i\) 的最小花费。
显然，转移方程：\(f(i) = \min (f(j)+(h_i-h_j)^2) + c\)，其中 \(j\in[1, i-1]\)。
我们假设决策点为 \(j\)，那么有 \(f(i) = f(j) + h_i^2 – 2h_ih_j + h_j^2 + c\)。
进一步将上式化为：\(f(j) + h_j^2 = 2h_ih_j + f(i) + c – h_i^2\)
我们记 \(y = f(j) + h_j^2, k=2h_i,x=h_j, b=f(i)+c-h_i^2\)。
那么这正好为 \(y = kx + b\) 的形式。
我们的目标是最小化 \(f(i)\)，这等价于最小化 \(b\)，也就是从维护的下凸壳中找到使直线的 \(b\) 最小的点即可。
对斜率优化不熟悉可以看看这个：//www.cnblogs.com/Tenshi/p/14481908.html
