HNOI2018 d2t3 那么水的树上DP都没看出来，让我意识到现在的DP水平可能还不如NOIP之前……去雅礼之前这个星期来复健一下……
仔细想想，我的省选算法除了网络流和树剖、平衡树之外真的没有学的特别好的…… NOIP的时候就是DP救了我……九省联考网络流却炸了……不管怎么说先搞搞DP吧
[HNOI2018] 道路
mmp当时在考场上把问题一般化为了多元函数的最值……写了个模拟退火，好像挂掉了……HN有神犇模拟退火A了…… 以及全部翻修公路70分什么鬼……（实际是75分，感谢yyb神犇教导 $\leftarrow$ 就是这个人模拟退火 A 了，膜拜）
Solution:
状态：f[u][x][y] 代表在节点 $u$ ，到根的路径上未翻修公路铁路数目为 $x, y$，子树内所有叶子的最小不便利值。
决策：如果 $u$ 是城市，考虑翻修公路还是铁路，直接从儿子转移，如果 $u$ 是乡村，直接就有 f[u][x][y] = ci * (ai + x) * (bi + y).
直接转移即可。
注意到答案需要long long，而它占用 8 Bytes ，所以直接开 DP 数组会 MLE！
DFS 的时候在栈里面开数组，然后把儿子的状态数组回传即可。这样状态数组的空间复杂度就是常数了。
[NOIP2017] 宝藏
要是这个题目出现在了 HNOI2018 ，保证我现在做不出来……然而 NOIP 的时候只用了 1h20min 就A了……真的气
Solution:
首先枚举打通地面的是哪个宝藏屋，以下称为根。
状态：设 f[S][u]为当前开凿了 $S$ 集合内所有点，且生成树满足总代价最小的时候，$u$ 到根的距离；g[S] 为当前开凿了 $S$ 集合内点，已开发部分的最小总代价（注意不是剩下部分的最小总代价，否则不满足无后效性，无法转移）。
决策：考虑枚举最后加入生成树的边。
于是一定有转移：
\[g(S) = \min_{S' \subseteq S} \{g(S') + L \cdot f(S', u)\}\] \[f(S, u) = \begin{cases} f(S', u) &\text{当}g(S)\text{不在}u\text{取得最小值} \\ f(S', v) + 1 &\text{当}g(S)\text{在}u\text{取得最小值},(u, v)\text{为原图中边} \end{cases}\]记忆化搜索即可。注意特判含有不包含根的连通块时，最小总代价为 $+\infty$.
[SDOI2009] 学校食堂
坑了6个月了……今天填上
回忆DP的要点：把转移需要的量放进状态
Solution: 状态：$f(i, j, S)$ 代表当前考虑第 $i$ 个人（Ta还没有吃饭），上一个吃到饭的是第 $j$ 个人，且 $i+1 \sim i+b_i$ 的人状态为 $S$，往后的最小代价。
决策：$i$ 吃到饭还是 $i+1 \sim i+b_i$ 中的一个吃到饭。如果是 第 $k$ 个吃到饭，则要综合考虑 $i \sim k-1$ 的限制。
转移：
\[f(i, j, S) = \min \begin{cases} f(i, k, S\cup\{k\}) + cost(j, k) \\ f(i', i, S') + cost(j, i) \end{cases}\]边界为 $f(n+1, *, \varnothing) = 0$.
复杂度为 $O(nb^22^b)$($b$为最大忍受度)，可以接受。
注意： 有一点非常坑！因为 $b_i \le 7$，所以可能一个人（称为甲）身后7个人都吃了饭Ta才吃，在Ta吃了之后吃的那个人不妨称为乙，则乙的坐标减去甲的坐标等于8！所以说转移的时候 $k$ 应该取 $[i-8, i+7] \cap \mathbb{Z}$ 内的所有值！
[NOIP2017] 逛公园
Solution:
DP+图论的好题，可惜考场上由于 $a \times b - a - b$ 的影响没能写出来=.=
先考虑70分部分分：
状态：$f(u, d)$ 表示当前在 $u$ 点，到 $n$ 点距离为 $d$ 的路径条数
决策：走哪个邻接点
转移：
\[f(u, d) = \sum_{<u, v> \in \mathbb{E}} f(v, d - \text{len}_{<u, v>})\]考虑如何实现：因为 $0 \le k \le 50$，所以有用的状态最多有 $O(nk)$ 个。比较暴力的做法是用一个map / unordered_map 存状态，但前者带 $\log$，后者有一定常数，都只能拿到 60 分。
稍微仔细想想就可以知道，如果 $\text{dist}_t[u]$ 为建立反图后的 $<u, t>$ 距离，那么只有 $d \ge \text{dist}_t[u]$ 时才可能有解，否则答案一定是0.（不可能有比 $<u, t>$ 最短路更短的路径！）这样的话，用数组 opt[200000+10][50+10] 即可存储（存储的时候第二维下标用 $d - \text{dist}_t[u]$）
再看满分做法：由于 0 边的存在，可能状态转移出现环，就不再满足动态规划 DAG 的要求了。我们发现，只有 0 环对此类决策有影响。我们考虑所有0边的导出子图，求出其上的所有强连通分量。如果某个强连通分量大小 $\ge 2$ ，那么它就是一个 0 环。（不一定是简单环，但这不影响）
考虑把这样的 0 环缩成 1 个点，称缩的某个点为 $P$。如果缩点后 $1 \sim P \sim n$ 的路径长度 $\in [\text{dist}_{s, t}, \text{dist}_{s, t}+k]$ ，那么显然有无穷多路径，否则这个 0 环对答案没有影响，可以删去。经过如此处理后就转化为了 70 分部分分的情况。至此问题解决。
[JLOI2014]天天酷跑
多段图路径问题，类似于[NOIP2014]飞扬的小鸟。
状态：设 $f(i, j, h, c)$ 代表在 $(i, j)$ 点，这次跳跃剩余上升高度 $h$ ，剩余连跳次数 $c$ ，从开始时到 $i-1$ 列的最大收益。
转移：设 $p, q$ 为最大连跳次数和最大跳跃高度。
- 分类讨论：
- $j > 1$：
- $h > 0$
- $j < m$ 时：$f(i, j, h, c)\rightarrow f(i+1, j+1, h-1, c)$ (继续上升)
- $h = 0$
- $j > 2$ 时：$f(i, j, h, c) \rightarrow f(i+1, j-1, 0, c)$ （下降）
- $j < m \text{ 且 } c > 0$ 时：$f(i, j, h, c) \rightarrow f(i+1, j+1, q-1, c-1)$ （连跳）
- $j = 2$ 时：$f(i, j, h, c) \rightarrow f(i+1, 1, 0, 0)$ （落地）
- $h > 0$
- $j = 1$：
- $j < m$ 时：$f(i, 1, 0, 0) \rightarrow f(i+1, 2, q-1, p-1)$ （起跳）
- $f(i, 1, 0, 0) \rightarrow f(i+1, 1, 0, 0)$ （走路）
注意：
- 空间开不下，用滚动数组，$i+1$ 之前把当前位置清理干净（不要把清理语句写在
if内！！！） - 刷表的时候，每到一个新的 $i$ ，就用 $-\infty$ 覆盖掉所有不可达位置
- 跑到 $n+1$ 才算结束
[WC2008]游览计划
最开始看上去有点像是求出一个类似虚树的东西：包含所有的关键点，而且总价值最小。
（后来才知道这玩意叫做斯坦纳树）
然后就去学习了一发= =
状态：$f(i, j, S)$ 表示以 $(i, j)$ 为树根，连通了景点集合 $S$ 的最小代价。
决策：
- 合并 $2$ 棵斯坦纳树
- 从上下左右的树根转移
转移：
- $f(i, j, S) = \min_{\varnothing \subsetneq S’ \subsetneq S}{f(i, j, S’) + f(i, j, S - S’) - \text{val}_{(i, j)}}$
- $f(i, j, S) = \min{f(i’, j’, S’) + \text{val}_{(i, j)}}$
边界：当 $(i, j)$ 为景点时，$f(i, j, (i, j)) = 0$.
注意到状态并不满足无后效性，所以说不能直接DP；发现如果采用刷表法的话，后一个操作相当于最短路中的松弛，所以可以用 SPFA 实现。
[HNOI2007] 梦幻岛宝珠
采用泛化物品合并解决。题解
[SCOI2014] 方伯伯的玉米田
一开始看到区间加法，想到差分后 &^#^%#%^$#@%#@% ，然后发现不仅复杂度爆炸，而且无法优化……
看题解第一行，看到一个并不显然的结论：拔高区间终点一定是 $n$.
证明：如果拔高区间的右侧还有数字的话，那么原来在 LIS 中的某些右侧数字在区间加法后可能离开 LIS ，答案肯定不如拔高区间右侧没有数字的情况好。
然后进行DP.
Solution:
状态：$f(i, j)$ 表示当前考虑第 $i$ 个玉米，已经拔高了 $j$ 次（这个玉米在 $j$ 个区间中）
决策：考虑前驱点、当前点拔高了几次（被坑了很久的一点：当前点可以多次拔高！）
转移：
\[f(i, j) = \max_{a_{i'} + j' \le a_i + j, j' \le j}f(i', j') + 1\]以 $j$ 为 $x$ 轴（需要平移 $1$ 个单位），$a_i + j$ 为 $y$ 轴，就转化为了二维数点。用二维数点的数据结构实现即可。
最开始写的二维线段树，T 飞；不服，写 zkw 线段树套 zkw 线段树，居然还 TLE ……
改成二维 BIT ，终于过了……
