NOIP DP
本章选用题目重做的方法进行复习
会选择有价值的题目重做
1. 数位DP
P2602 数字计数
Trick 典型转换：前缀和转换
通过从高到第枚举数字的方法进行统计。这是很常见的限制数字范围的方法。
P4127 同态分布
所以数位 DP 开始推导的时候通常是从暴力开始的，开始的时候就是枚举数的构成，然后才改进成有子问题重合的形式，才真正能够用记忆化搜索优化。
本题在处理非常特殊的这种模一个变量的问题的关系，但是这个变量的可能性不多，所以采用直接枚举的方式处理。
2. 状压DP
状压这种思路本身是用来表示集合的。通常用到状压有以下情况：表达使用状态（90%）、轮廓线
P3694 邦邦的大合唱站队
本题要先把视角从个人视角转移到集体视角，因为一个人是否要出队和他的集体摆放的位置是有关系的，而这个摆放位置可以通过一一钦定的方式进行枚举。
3. 树形 DP
P2607 骑士
显然的基环树描述，但是这不就是最大独立集——没有上司的舞会吗？？
大无语，搬到基环树上无非分树和环处理或者考虑强制断边，结果难度直接三级跳。
P3698 小 Q 的棋盘
像步数这种有固定大小的东西都可以看成是一种费用，是的这是一道树形背包，显然应该分成要回到根和不回到根两种情况
P3177 树上染色 [!]
这里涉及树上背包问题一个很重要的优化：上下界优化
首先考虑点对之间的路径是非常难处理的，所以要考虑从处理点对贡献变成处理边的贡献
然后就发现选择点又可以看成费用，然后就可以直接树形背包。
然鹅，这里还要考虑上下界优化，这种优化通过子树大小限制枚举的范围，这个能够去掉一个 n。注意要考虑下界，就是去掉当前子树之后其他部分能不能选够 j-k 个
4. 虚树 DP
虚树 DP 经常被用来解决与树上关键点相关的问题。
首先明确两种建立虚树的方式：
-
两次LCA法：先按照DFN排序，并将相邻点的LCA加入，然后再排序并去重，此时已经有了表达所有父子关系的所有需要的LCA，然后相邻两点 \(x,y\) 求 \(l=\mathbf{LCA}(x,y)\) 并且连边 \(l\to y\)
-
栈维护法：用栈维护当前链，按照 DFN 序“从左往右”扫过树，出栈的时候加边。
P3233 世界树 [!]
令 \(f_k[x]\) 表示在 \(k\) 为根的情况下 \(x\) 在它的子树内能够管辖多少点（不论它是不是关键点）
那么，我们成功地发现这样是做不出来的。
但是如果求每个点子树内距离最近的关键点是可以的
所以我们可以建立虚树，对于虚树上面有的点，直接换根 DP 就可以得到 \(g[x]\) 表示距离 \(x\) 最近的关键点。那么现在考虑没有在虚树上面的点，发现这样的点有两种:
-
被压缩在某一条虚树边上，这个好办，对于虚边 \((p,q)\) 上面的点，肯定一半贡献到 \(g[p]\) 另一半贡献到 \(g[q]\) （这个分界点可以倍增）
-
如果一棵子树（假设它是虚树上点 \(p\) 的儿子）之内完全没有关键点，那么这棵子树完全不会出现在虚树上，不过他们肯定全部都会贡献到 \(g[p]\)
5. 仙人掌上 DP
这种题少，但是恶心
P4410 无归岛
点名表扬无归岛。
这道题不能算典型的仙人掌 DP，因为这个题的图只有一个大环和若干三角环，不过我应该写了一个通用的方案。
仙人掌 DP 有两种解法：
-
DFS 树转化
-
圆方树转化（注意：Tarjan建圆方树有一个性质，那就是它建出来方点的连边次序是根据 dfn 序的）
6. 数据结构优化 DP
P2605 基站选址
考虑先推普通 DP，显然的想法就是枚举上一个基站在哪里。
Trick 等效决策法，最开始也许你会想到 \(f_{i,j}\) 表示前 \(i\) 个村庄里面有 \(j\) 个，但是马上就会发现这样无法转移，所以实际上限定第 \(j\) 个基站就是放在 \(i\) 是完全等效的，这样就可以处理
然后发现过不去，考虑优化，通常数据结构优化就是把一段求和或者取min放到数据结构上快速处理，这个题可以考虑把要枚举的转移部分直接放进线段树，考虑阶段发生改变，即添加了一个村庄之后如何维护最小值，观察发现，一个村庄需要支付赔款的转移是一个区间，即右边也覆盖不到，左边也覆盖不到的时候，所以维护左右边的覆盖边界，当当前阶段超过右边界，那么这个村庄就不能再被后续的右边基站覆盖，此时只能靠左边去覆盖，如果左边也不能覆盖，即如果从 \(f[1\to (L[x]-1)]\) 转移，那么就要支付罚款，所以给前面这个段添加他的代价。
P3287 方伯伯的玉米田
这是一道方伯伯题
首先模拟操作，我们发现，同时拔高这个操作并不会改变区间内的相对位置，然而我们的最终目标是获得最长的不下降子序列，那么我们肯定就是要拔高右边使得他们高于左边，然而区间长度与费用是没有关系的，所以，一段拔高的操作区间的右端点肯定是最右边。
然后就变成了一个三维的求和，其中一位可以通过枚举顺序的方式保证，另外两位可以开二维树状数组。
7. 单调队列优化 DP
单调队列优化 DP 适用于对于某一决策，其限定范围呈单增函数（滑动窗口，至少要满足这个范围不会使得一个决策出范围之后再进来）变化，并且，满足内层维护的代价 \(\mathbf{cost}(i\to j)\) （即用 \(i\) 贡献 \(j\) 的代价）函数能够分成只关于 \(i\) 和只关于 \(j\) 的部分，就是说随着状态的推进决策集合的最优性相对不变，因为在变动的 \(j\) 的部分大家都是一样的） 的 DP
能够排除出候选集合的决策 \(x\) 一定要满足以下特征：存在一个元素 \(p\) ，有：
-
比 \(x\) 更合法，那么， \(x\) 在候选集合内的时候 \(p\) 肯定也在，然而 \(x\) 出候选区之后 \(p\) 还在，自然，所有使用 \(x\) 的转移都可以等价替换成使用 \(p\)
-
比 \(x\) 对于当前状态更优
P2254 瑰丽华尔兹 [!]
不要一开始就把题目限制代入，不要设计状态的时候就考虑时空限制
首先我们得到一个显然的转移是 \(f[t][x][y]=\max\{f[t-1][x][y],f[t-1][x'][y']+1\}\) 其中 \((x',y')\) 是上一个位置（有可能不存在，也许上一个位置是一个家具）
但是我们发现 \(T\) 太大了，不过 \(K\) 又很小，所以考虑用 \(K\) 设计状态：
\[f[t][x][y]=\max_{(i,j)}\{f[t-1][i][j]+\mathbf{distance}\{(x,y),(i,j)\}\} \]其中 \((i,j)\) 是在第 \(t\) 个时间段内能够转移到 \((x,y)\) 的位置
对，然后看起来我们没有优化时间，不过，如果分别写出 \((i,j)\) 的范围，我们就发现这是一个经典的滑动窗口问题，然后我们的代价函数 \(\mathbf{cost}(i\to j)=\mathbf{distance}(i,j)=j-i\) 这是满足上面的性质的。
8. 斜率优化 DP
如果方程式里面只有一个 ij 的乘积项，那么我们可以通过把方程变成直线，最优化截距来进行转化，故可以维护决策点凸壳，根据x坐标和斜率的不同变化趋势，我们有不同的维护方式。
9. 动态 DP
动态 DP 主要用于解决一类问题。这类问题一般原本都是较为简单的树上 DP 问题/序列上，但是有修改点权的操作和多次询问。
P4719 【模板】动态 DP
又是你，没有上司的舞会
题意即要修改点权，多次询问树上最大权独立集。
要带修，考虑用动态 DP。如果要修改，就必须考虑要维护 DP 的转移过程。
而矩阵就是个很好的方法，就比如如果要维护连分数的值，支持单点修改和查询值，矩阵就很好用了。
但是原来的方程有求和符号，不好处理，这个时候，可以分成轻儿子和重儿子来处理，这样就没有求和符号，可以用较小的矩阵表示。
修改的时候，从下面往上传递矩阵乘法的信息，保证一条链的链底保持了下面所有儿子传上来的信息，这时求第一条链的区间乘法就得到了答案。
标签：NOIP,枚举,考虑,树上,优化,虚树,DP From： https://www.cnblogs.com/haozexu/p/18299314