Economic One-way Roads
dp中常见的问题分为最值与计数两种，两个问题有共同之处亦有不同之处。
-
最值问题：\(min,max\) 是不可逆不可减满足结合律交换律的运算，且运算具有可重性，常见的优化思路是通过可重性打包信息进行转移。与计数不同的，最值问题只需要考虑不漏。
-
计数问题：计数问题要做到不重不漏，但 $+,\times $ 具有良好的性质，通过可减性可以完成“先算全集，再减去不合法”这件事，于是便有了容斥。
此题为最优问题，有向图的强连通计数是典，但是求最小值就不能容斥了，相对的，不再要求转移顺序且可被多次贡献。
考虑对于强连通的点集 \(S\) ，加一些点使得它任然强连通，那可以加一条链，且起点终点属于 \(S\) 。
注意到，任意一个强连通点集都可通过一个点进行若干次加链得到。
这种方法被称为耳分解，加的路径被称为耳。
每次加一条链需要枚举子集，此题可以每次在链的两端扩栈一个点，且在最后一步将两端连起来。
记录状态 \(f_s\) 表示点集 \(s\) 形成强连通的代价，\(g_{s,i,j}\) 表示当前点集为 \(s\) 且 \(i\) 与 \(j\) 连成链后就连通。
时间复杂度：\(O(2^nn^3)\) 。
Sort and Match
计数问题中一类需要对一些抽象的东西计数，比如在某个变换下等价类个数（AT常考）、抽象图的个数（欧拉回路等）、本质不同字符串等，这类东西不好直接计数，可以将每种方案找到唯一映射，这类映射一般用到贪心和最优化思想，再对贪心的结构去dp。
此题是对边有编号的欧拉回路计数，欧拉回路的充要条件很难直接去dp，考虑将每个欧拉路径转化成其字典序最小的一条路径，dp过程按边标号的顺序从小到大去加欧拉回路。
由于此题要钦定第一条边，所以倒着dp，总之是好做的，时间复杂度 \(O(n^4)\) 。
Crossing the Border
折半思想，本质是平衡复杂度。
\(O(3^n)\) 的子集枚举的转移是简单的。
考虑对原集折半，形如 \(S -> S'\) 的转移变成 \((L,R) ->(L',R')\) 转移，为了初状态和末状态的平衡性，枚举 \(L,R'\) 。