讲师：钟皓曦，NOI2012Au，from 成都七中
dp
树形dp
核心：在树上做的 dp
给定一棵 \(n\) 个点的树，求这棵树有几个点。
对于树形 dp，第一个维度是 \(f_i\)，代表以 \(i\) 为根的子树内的信息（有几个点）
树形 dp 的转移方法是把所有儿子信息整合
所有儿子的 dp 值 \(\rightarrow\) 自己。
转移：\(f_i=f_{son1}+f_{son2}+\ldots +f_{son_n}+1\)
答案：\(f_1\)
树形dp利用dfs实现
给定一棵 \(n\) 个点的树，每条边有边权，定义 \(dist(i,j)\) 代表 \(i\rightarrow j\) 的路径长度，求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^ndist(i,j)\)，数据范围 1e6。
\(f_i\) 代表 \(i\) 这棵子树内的答案。
考虑一条边被经过几次。什么时候会经过这条边？显然，\(i,j\) 一定要一个在外面，一个在里面。
令 \(f_i\) 代表子树大小，一条边连接 \(i\) 与其父亲的边被经过的次数就是 \(2\times f_i\times (n-f_i)\)。（乘法原理）
注意两个点可以换顺序，所以应 \(\times 2\)。
给定一棵 \(n\) 个点的树，有边权，求 \(max_{i,j}dist_{i,j}\)，1e6。
其实是求树的直径。
如果边权非负，两点一定都是叶子节点。
令 \(f_i\) 代表子树内**距离 \(i\) **最远的距离，\(g_i\) 代表次远的距离。
树上路径组成：起点+终点+LCA
答案：\(\max_{1\le i\le n}(f_i+g_i)\)，这里做的是枚举 LCA。
如何考虑转移？
画一个数轴，观察当前值 dis 与 \(f_{now}\) \(g_{now}\) 的位置关系。
求树的最大独立集，没有上司的舞会。
最大独立集：选出尽量多的点，使得它们不相邻。
把根节点染成黑色，子节点染成异色，不断染，统计黑白数量，这是错误的，但告诉我们树是二分图。
证明一件事错误是很困难的，但举出反例是容易的
令 \(f_i\) 代表子树内根节点染色的情况下最大独立集，\(g_i\) 代表不染色的情况下最大独立集。
发现 \(i\) 是否染色，会根据儿子是否染色。
dp中可以把所有想知道的事记到状态里
考虑 \(f_i\) 的转移。
此时儿子肯定都不能选，\(f_i=1+\sum\limits_{k=1}^mg_{son_k}\)
对于 \(g_i\)，儿子可选可不选，所以 \(g_i=\sum\limits_{k=1}^m\max(f_{son_k},g_{son_k})\)
ppt 41 P5 poj463
利用上一题的思想。令 \(f_i\) 代表没有士兵，由儿子守护。
对于 \(i\) 点，如果不放士兵，所以要不是儿子保护它，要不然就是父亲守护它，增加 \(h_i\) 代表没有士兵，但是由父亲守护。
对于 \(f_i\) ，至少一个儿子要有士兵。
令 \(p_{i,0/1}\) 代表前 \(i\) 个儿子，是否有士兵，————————————。
建议看代码，讲的有点快。
树形dp常见手段——将所有儿子信息合并时，往往需要另一个dp辅助合并
\(f_i=\sum\limits_{k=1}^m\)
\(g_i=1+\sum\limits_{k=1}^m\min(f_{son_k},g_{son_k},h_{son_k})\)
\(h_i=\sum\limits^mf_k\)
状压dp
核心思路：把 \(n\) 个数压缩成一个数
二进制状态压缩——只有 0/1 两种取值
ppt 60 P1 吃奶酪
用 \(n\) 位的二进制数表示每个点是否走过，这个二进制数 \(\le 2^n\)。
令 \(f_{S,i}\) 代表每个点状态集合为 \(S\) 时终点是 \(i\) 的情况下的最小距离。
初始化：一开始把所有值标记成 double_inf ，\(f_{1,0}=0\)
判断集合中的状态：i&(1<<j)
合并状态：chkmin(f_{1|(1<<k),k},f_{i,j}+dis_{j,k})
把 bool 数组变成一个数
注意最后加答案要走回 \(0\) 号点。
复杂度 \(O(2^N\times N^2)\)
状压的题范围不会很大 \(\rightarrow\) 范围不是很大的题可能会是状压。
ppt 61 P2 P1879
一个格子能不能种草：上一行种没种，这一行有没有相邻的种草。
\(f_{i,j}\) 表示前 \(i\) 行已经种好草，第 \(i\) 行的种草情况为 \(j\) 时的方案数。
枚举下一行的种草情况，统计方案数。
K 国王问题 P1896
与上题的不同——国王数量
多一个条件 \(\rightarrow\) 加一个维度
\(f_{i,j,k}\) 代表前 \(i\) 行种草情况为 \(j\) ，已经用了 \(k\) 个国王的方案数。
剩下一致。
ppt 118 P6 CodeChef LEMOUSE
令 \(f_{i,j}\) 代表走到 \((i,j)\) 最少老鼠数。
经典题，方格取数。
但是显然不对。
令 \(f_{i,j,0/1,0/1}\) 代表走到 \((i,j)\) 时，上一步是向右/下，上两步向右/下走。
考虑到被同一只老鼠反复吓到中间过程最多走两步。
复杂度 \(O(4n^2)\)
ppt 124 P9 P2051
放炮要规定一个顺序——一行一行放
讨厌计数题
令 \(f_{i,j,k}\) 代表放到第 \(i\) 行时，有 \(j\) 列放了 \(0\) 个炮，有 \(k\) 列放了 \(1\) 个炮。
显然，有 \(m-j-k\) 列放了两个炮。
对于第 \(i\) 行，可以放 \(0\sim 2\) 个炮。
\(0:f_{i,j,k}+=f_{i-1,j,k}\)
\(1:f_{i,j,k-1}+=f_{i-1,j,k}\times k,f_{i,j-1,k+1}+=f_{i-1,j,k}\times j\)
对于放两个炮的情况，有三种情况进行转移。
标签：代表,limits,day4,son,寒假,2.5,times,sum,dp From： https://www.cnblogs.com/BYR-KKK/p/18007660