这份 dp 题单的最后几题好难 orz。

前面的题比较简单，所以我会选取一些题来讲，其它的直接看代码理解吧 qwq。

https://atcoder.jp/contests/dp

https://atcoder.jp/contests/dp/submissions?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi

这道题不同于常规的背包问题，因为背包容量很大，我们不能对容量进行 dp，但注意到全部的收益加起来不超过 \(10^5\)​，想到用 \(f(j)\)​ 表示收益至少为 \(j\)​ 时的最小容量花费。记当前在第 \(i\) 个物品，有状态转移方程：

\[f(j) = \min(f(j), f(j-v_i)+w_i)
\]

注意到每碟寿司数量最多 \(3\)​​​ 个，不难想到用 \(f(x, y, z)\)​​​ 表示当前有 \(x\)​​​ 盘寿司数量为 \(3\)​​​，\(y\)​​​ 盘寿司数量为 \(2\)​​​，\(z\)​​​ 盘寿司数量为 \(1\)​​​​ 时距离吃完全部寿司的期望步数。

根据全期望公式，我们有：

\[f(x, y, z) = (1-\frac{x+y+z}{n})f(x, y, z) + \frac{x}{n}f(x-1, y+1, z) + \frac{y}{n}f(x, y-1, z+1) + \frac{z}{n}f(x, y, z-1)
\]

根据上述公式进行记忆化搜索即可，细节见代码。

注意到 \(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))\)​​

\(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)\)​。

\(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)\)​​​。

倍增 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(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\)，用矩阵快速幂加速这个过程就好了。

数位 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)\)​​

思路比较新颖的 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\)​，变换前后的合法方案是一一对应的。

\(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)\)。

换根 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'\)​​ 值的前缀积和后缀积。

个人感觉这道题是这份题单中最难的了 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\) 进行更新。

用什么可以高效维护上述数轴上的操作呢？线段树可以做到，也就是区间加以及区间最大值查询。

排序 + 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]\)。

与背包问题一样，可以减少一维空间。

组合计数 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)\) 看成是障碍点即可。

斜率优化 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\) 最小的点即可。

对斜率优化不熟悉可以看看这个：https://www.cnblogs.com/Tenshi/p/14481908.html