DP（动态规划）

考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $n$ 个点的无根树。

类似有向无环图的拓扑排序，可以定义一种无根树的“拓扑排序”：每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 $r$，则当最终剩余一个孤点时，直径 $d=2r$，否则直径 $d=2r-1$。为了生成无根树，我们考虑进行逆操作，在当前的树上加叶子。在此之前，为了不重不漏地对无根树进行表示，我们考虑如下的唯一表示方法：设 $\text{dis}(x)$ 为节点 $x$ 在添加叶子过程中第几轮被添加上树的。对于$S=\{x\mid \text{dis}(x)=\text{const}\}$（也即同一层的节点），显然两棵有标号无根树同构但标号不同，当且仅当每个上述节点$x$的叶子节点的标号集合不同。我们总是将 $x$ 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构，子节点编号集合相同导致重复计数的问题”。同时，为了方便、准确地计算，我们严格规定，新加入的 $k$ 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 （更多…）

看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。

例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）

再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。

这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。

是的，又是一道考试时想出正解没有打出来的题目

货物分组 – 牛客网

根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。

（更多…）

洛谷题库 P2569 [SCOI2010]股票交易

设 $f(i,j,0/1/2)$ 表示第 $i$ 天持有 $j$ 支股票，并且当天进行了 持有 / 买 / 卖 操作，所能获得的最大的收益。很容易想到以下转移：

$$\begin{aligned}&f(i,j,0) = \max \{f(k,j,t) \mid k < i,t\in\{0,1,2\}\}; \\ &f(i,j,1)= \max \{f(k,p,t) \mid k < i-w, p \leq j,t\in\{0,1,2\}\}; \\ &f(i,j,2)= \max \{f(k,p,t) \mid k < i-w, p \geq j,t\in\{0,1,2\}\} \end{aligned}$$

（更多…）