by TheBigYellowDuck
涵盖了很多类型的 dp 问题，做一做还挺有趣的。
做这个题单的时间跨度长达一年。
为了完整性写了一些简单题。
A Frog 1
设 \(f(i)\) 为跳到第 \(i\) 格上的最小花费，由于只能向后跳两格，容易写出转移方程
\[f(i)=\min\{f(i-1)+|h_i-h_{i-1}|,f(i-2)+|h_i-h_{i-2}|\} \]时间复杂度 \(\mathcal{O}(n)\)。
B Frog 2
和 A 没什么区别。
设 \(f(i)\) 为跳到第 \(i\) 格上的最小花费，容易写出转移方程
\[f(i)=\min\limits_{i-k\leq j<i}\{f(j)+|h_i-h_j|\} \]时间复杂度 \(\mathcal{O}(nk)\)。
C Vacation
设 \(f(i,j)\) 为在第 \(i\) 天进行第 \(j\) 种活动的答案。容易写出转移方程
\[f(i,j)=a_{i,j}+\sum\limits_{k\neq j} f(i-1,k) \]时间复杂度 \(\mathcal{O}(n)\)。
D Knapsack 1
01 背包的板子。
设 \(f(i,j)\) 为用体积为 \(j\) 的背包装前 \(i\) 个物品获得的最大价值，容易写出转移方程
\[f(i,j)=\max\{f(i-1,j),f(i-1,j-w_i)+v_i\} \]时间复杂度 \(\mathcal{O}(nW)\)。
E Knapsack 1
还是 01 背包，但是 \(W\leq 10^9\)。
注意到 \(v_i\leq 10^3\)，也就是说获取的最大价值不会很大，考虑从这个角度设计状态。
设 \(f(i,j)\) 为在前 \(i\) 个物品中获得价值为 \(j\) 的最小体积。转移方程为
\[f(i,j)=\min\{f(i-1,j),f(i-1,j-v_i)+w_i\} \]从 \(\sum v_i\) 开始从大到小枚举，第一个满足 \(f(n,j)\leq W\) 的 \(j\) 就是答案。
时间复杂度 \(\mathcal{O}(n\sum v_i)\)。
F LCS
最长公共子序列问题。
设 \(f(i,j)\) 为 \(S\) 的前 \(i\) 个字符和 \(T\) 的前 \(j\) 个字符的最长公共子序列，容易写出转移方程
\[f(i,j)=\left\{ \begin{aligned} &f(i-1,j-1)+1 && (S_i = T_j) \\ &\max\{f(i-1,j),f(i,j-1)\} && (S_i \neq T_j) \end{aligned} \right. \]输出方案直接记录决策方式即可。
时间复杂度 \(\mathcal{O}(|S||T|)\)。
G Longest Path
有向无环图中最长链问题。
设 \(f(u)\) 为终点为 \(u\) 的最长链长度。一边拓扑排序一边 dp 就可以了。
转移方程为
\[f(v)=\max\limits_{(u,v)\in E}\{f(u)+1\} \]时间复杂度 \(\mathcal{O}(n)\)。
H Grid 1
憨憨题。设 \(f(i,j)\) 为走到格子 \((i,j)\) 的方案数，转移方程为
\[f(i,j)=f(i-1,j)+f(i,j-1) \]时间复杂度 \(\mathcal{O}(HW)\)。
I Coins
设 \(f(i,j)\) 为前 \(i\) 枚硬币中有 \(j\) 枚正面朝上的概率。转移方程为
\[f(i,j)=f(i-1,j-1)\times p_i+f(i-1,j)\times (1-p_i) \]注意边界 \(j=0\) 的处理即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
J Sushi
注意到每盘寿司的个数非常少，并且寿司数目一样的盘子等价，不难联想到这道题。
不妨借鉴这道题的状态设计。设 \(f(i,j,k)\) 表示当前还剩 \(1\) 个寿司的盘子有 \(i\) 个，还剩 \(2\) 个寿司的盘子有 \(j\) 个，还剩 \(3\) 个寿司的盘子有 \(k\) 个的操作期望此时空盘子有 \(n-i-j-k\) 个。
转移方程为
\[f(i,j,k)=1+\dfrac{n-i-j-k}{n}f(i,j,k)+\dfrac{i}{n}f(i-1,j,k)+\dfrac{j}{n}f(i+1,j-1,k)+\dfrac{k}{n}f(i,j+1,k-1) \]移项即有
\[f(i,j,k)=\dfrac{1}{i+j+k}\times\left(n+i\times f(i-1,j,k)+j\times f(i+1,j-1,k)+k\times f(i,j+1,k-1)\right) \]时间复杂度 \(\mathcal{O}(n^3)\)。
K Stones
简单博弈题。令 \(f(i)=1\) 表示先手必胜，否则后手必胜。
考虑基本的必胜状态，显然有 \(f(0)=0\)。
对于每一个 \(x\)，我们让 \(x+a_i\) 或上与 \(x\) 相反的状态即可。
时间复杂度 \(\mathcal{O}(nk)\)。
L Deque
发现任意时刻留在队列中的数一定是一个连续区间，考虑以其设计状态。
设 \(f(l,r)\) 为区间 \([l,r]\) 留在队列内的答案。此时先手取会希望答案尽量大，后手取会希望答案尽量小。
转移方程为
\[f(l,r)=\left\{ \begin{aligned} \max\{f(l+1,r)+a_l,f(l,r-1)+a_r\}, && n-(r-l+1)\equiv 0 \pmod 2\\ \min\{f(l+1,r)-a_l,f(l,r-1)-a_r\}, && n-(r-l+1)\equiv 1 \pmod 2 \end{aligned} \right. \]采用区间 dp 的方式来做这个过程，但是不需要枚举断点。
时间复杂度 \(\mathcal{O}(n^2)\)。
M Candies
容易想到设 \(f(i,j)\) 为前 \(i\) 个人分 \(j\) 个糖果的方案数，转移方程为
\[f(i,j)=\sum\limits_{k=\max\{0,j-a_i\}}^j f(i-1,k) \]暴力转移时间复杂度 \(\mathcal{O}(nk^2)\)。
发现上式是一个区间求和，考虑前缀和优化。
令
\[sum_j=\sum\limits_{k=0}^j f(i-1,j) \]转移方程为
\[f(i,j)=sum_j-sum_{j-a_i-1} \]时间复杂度 \(\mathcal{O}(nk)\)。
N Slimes
经典合并石子问题。
设 \(f(i,j)\) 为把区间 \([i,j]\) 合并为一个数的最小代价，合并 \([i,j]\) 一定是从两个小区间合并而来，操作代价为 \(s(i,j)=a_i+a_{i+1}+\cdots+a_j\)。
转移方程为
\[f(i,j)=\min\limits_{i\leq k<j}\{f(i,k)+f(k+1,j)+s(i,j)\} \]时间复杂度 \(\mathcal{O}(n^3)\)。
O Matching
观察到数据范围很小，考虑状压 dp。
设 \(f(i,S)\) 为前 \(i\) 个左部点匹配的右部点集合为 \(S\) 的方案数。
考虑 \(i\) 可以匹配的所有满足 \(j\in S\) 的右部点 \(j\) ，在这次匹配之前 \(S'=S-\{j\}\)，转移方程为
\[f(i,S)=\sum\limits_{j\in S} f(i-1,S')[a_{i,j}=1] \]由于是完美匹配，所以有 \(i=|S|\)。转移可以少枚举一层。
时间复杂度 \(\mathcal{O}(n2^n)\)。
P Independent Set
树上独立集计数，其实很类似这道题。
设 \(f(u,0/1)\) 表示在 \(u\) 的子树中并且 \(u\) 染白/黑的答案。枚举 \(u\) 的子节点 \(v\)，转移方程为
\[f(u,0)=\prod f(v,0)+f(v,1) \]\[f(u,1)=\prod f(v,0) \]时间复杂度 \(\mathcal{O}(n)\)。
Q Flowers
一眼最长上升子序列。
设 \(f(i)\) 表示以 \(i\) 结尾的答案。转移方程为
\[f(i)=\max\limits_{j=1}^{i-1}\{f(j)[h_j<h_i]\}+a_i \]朴素转移时间复杂度 \(\mathcal{O}(n^2)\)。
注意到上式为一个区间最值的形式，考虑线段树优化。在线段树上 \(h_i\) 的位置上更新 \(f(i)\) 的值，转移只需查询 \([1,h_i]\) 的最大值即可。
时间复杂度降至 \(\mathcal{O}(n\log n)\)。
R Walk
图中长度为 \(k\) 的路径数量即为邻接矩阵 \(k\) 次幂矩阵中的所有元素和。
证明可以归纳：
-
当 \(k=1\) 时，显然成立。
-
假设 \(k=m\) 成立，想证明 \(k=m+1\) 成立。
设原图邻接矩阵为 \(A\)，则 \(A^{m+1}=A^mA\)。考虑矩阵乘法的定义。
\[A^{m+1}_{ij}=\sum\limits_{k=1}^n A^m_{ik}A_{kj} \]由归纳假设，其中 \(A^m_{ij}\) 的意义为由 \(i\) 至 \(k\) 的长度为 \(m\) 的路径长度，\(A_{kj}\) 的意义为由 \(k\) 至 \(j\) 的长度为 \(1\) 的路径长度。由乘法原理显然正确。
从而只需要跑一遍矩阵快速幂即可。
时间复杂度 \(\mathcal{O}(n^3\log k)\)。
S Digit Sum
数位 dp。
设 \(f(d,r,0/1,0/1)\) 表示考虑到从低到高的第 \(d\) 位，数位之和模 \(D\) 的余数为 \(r\)，没有/有卡上界，没有/有全为前导 \(0\) 的方案数。按照数位 dp 的套路转移即可。
时间复杂度 \(\mathcal{O}(D\lg K)\)。
T Permutation
需要注意的一点是，我们不关心数值的具体大小，只需要知道它们之间的相对关系。
考虑 dp。设 \(f(i,j)\) 为考虑前 \(i\) 个位置，且在第 \(i\) 个位置上填了当前第 \(j\) 小的数的方案。边界是 \(f(1,1)=1\)。转移只需要考虑 \(i\) 与 \(i-1\) 的大小关系。
\[f(i,j)=[a_i>a_{i-1}]\left(\sum_{j'=1}^{j-1}f(i-1,j')\right) \]\[f(i,j)=[a_i<a_{i-1}]\left(\sum_{j'=j}^{i-1}f(i-1,j')\right) \]注意下标。在第二个式子中，上一次第 \(j\) 小的数现在变成了第 \(j+1\) 小的数，应该统计进来。
朴素转移是 \(\mathcal{O}(n^3)\) 的。这个式子很容易用前缀和优化，可以做到 \(\mathcal{O}(n^2)\)。
U Grouping
子集 dp。
设 \(f(S)\) 表示将集合 \(S\) 分为若干组的最大收益。预处理 \(g(S)\) 表示将 \(S\) 分为一组的收益，则有
\[f(S)=\max_{T\subseteq S}\{f(T)+g\left(\complement_ST\right)\} \]时间复杂度 \(\mathcal{O}(n^22^n+3^n)\)。
V Subtree
W Intervals
X Tower
经典贪心。
在已经放好的箱子的集合确定时，我们希望能继续往上放的箱子越多越好。
考虑最下面的两个箱子 \(i,j\)，若将 \(i\) 放在下面，则还有 \(s_i-w_j\) 的承受能力，反之还有 \(s_j-w_i\) 的承受能力。如果 \(i\) 放在下面更优，则有
\[w_i+s_i>w_j+s_j \]我们按照 \(w+s\) 从小到大排序，从上到下决策应该放什么。这样就变成了 01 背包问题。
设 \(f(i,j)\) 表示考虑前 \(i\) 个箱子，当前总质量为 \(j\) 的最大价值。可以倒序循环压掉第一维。
时间复杂度 \(\mathcal{O}(\sum s_i)\)。
Y Grird 2
据说是典题，但是我没见过。
先对所有障碍排序，设 \(f(i)\) 表示走到第 \(i\) 个障碍且不经过其他障碍的方案数。
考虑容斥。枚举所有 \(x_j\leq x_i\) 且 \(y_j\leq y_i\) 的障碍 \(j\)，钦定从 \((1,1)\) 走到 \(j\) 碰到第一个障碍，从 \((x_j,y_j)\) 到 \((x_i,y_i)\) 随便走，则有
\[f(i)=\binom{x_i+x_j-2}{x_i-1}-\sum_j f(j)\binom{x_i+y_i-x_j-y_j}{x_i-x_j} \]把终点看作第 \(n+1\) 个障碍，按照一样的方法统计答案即可。
时间复杂度 \(\mathcal{O}(n^2+H+W+\log p)\)。
Z Frog 3
设 \(f(i)\) 表示跳到 \(i\) 上的最小花费。转移方程为
\[f(i)=\min_{j<i}\{f(j)+(h_i-h_j)^2+C\} \]一眼斜率优化。分离变量。
\[f(i)-h_i^2-C=\min_{j<i}\{f(j)+h_j^2-2h_ih_j\} \]令
\[\left\{ \begin{aligned} y_j&=f(j)+h_j^2 \\ x_j&=h_j \\ k_i&=2h_i \\ b_i&=f(i)-h_i^2+C \end{aligned} \right. \]则有
\[b_i=\min_{j<i}\{y_j-k_ix_j\} \]斜率优化。时间复杂度 \(\mathcal{O}(n)\)。
标签：方程,limits,Contest,sum,转移,mathcal,复杂度,DP From： https://www.cnblogs.com/duckqwq/p/18132128