OI, 梦开始的地方。
$n$小，搜索或者状压。
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态，$dp(S)$为在$S$状态时的最优解，然后转移就是
$$dp(S) = min(dp(S-g(i,j))+1)$$
初始化$g(i, j)$需要用待定系数法求出抛物线，即解二元一次方程，这个推一推就能推出通解了，复杂度$O(n^3)$
然后DP求解的时候是$O(2^nn^2)$，有一点大，所以会TLE了几个点，有空补补$O(2^nn)$做法
搜索做法：
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态，然后DFS，加可行性剪枝
DFS里每次看正在搜索的点是否已经被前面打了，用二进制优化，不然就和后面的相连或者一炮只打这一只小鸟，然后更新答案即可，这样做是满分的
设$dp(i,j,0)$为前$i$个课程申请$j$次，第$j$次成功的最小体力期望，$dp(i,j,1)$为前$i$个课程申请$j$次，第$j$次不成功的最小体力期望。
转移方程具体看代码，太长了，不在这里重复打
注意double别用memset并且赋值考虑是否会溢出
BZOJ 1001
直接建图dinic，注意这题坑多
1 存边不要用vector，vector自动申请内存在不够的时候会申请多一倍，所以换数组或者reserve
2 原图是无向图，所以反向弧容量也是$c$而不是0
3 注意$n,m$和点就行
本题如果是删边就是裸最小割，但是是删点我们就要考虑拆点了。
我们把一个点$i$拆成$i$(入点)，$i+n$(出点)。
入点专门负责接受其他节点的入边，出点专门负责连出边。
然后我们使$i->i+n$，容量为1，意义为删掉一个点的需要的价值，这样就可以删点了
然后为了连通，如果原图$i->j$，那么就连$i+n->j, j+n->i$，容量为$INF$，因为这些边不能影响流量。
然后从$s+n$到$t$做最大流即为答案。
(并且$f(u,v) \leq c(u,v))$
Dinic算法的大致思路：
1 先BFS对残量网络进行分层(根据从$S$到点$i$的距离分层，这些和$S$距离相等的点$i$都是一层的)。(初始的图也算一个残量网络)
2 然后再DFS进行多路增广(好处是如果两条不同增广路很长，但是重合了一大半，就不用两次BFS)，如果增广到了$T$或者当前最大可改进量(最小残量)等于0就要终止DFS，否则在残量网络上进行增广，必须按照层次来增广，如果路径可以增广，那么路径上的边流量加去最大可改进量(最小残量)，反向弧减去最大可改进量(最小残量)，因为流量平衡。
还可以进行优化，当前弧优化。如果一个点已经增广了一些边，那么这些边在下次DFS的时候不需要再被考虑。
Dinic模板代码见相关代码部分。loj #101
相关学习文章
写时注意：
1 边数组大小。(有一次ins就得乘一次2，最好用vector存)
2 拆点后点数组大小。
3 加边的时候如果无向，则反向弧容量为$c$，否则为$0$
最小割的流量$f(s,t)$=最大流
在找不到增广路之后，分层了的节点就是 $S$，没分层的点就是 $V-S=T$，即$s-t$割中的两个不相交集合${S, T}$
最大流$flow$是$s-t$最大流，$(S, T)$是$s-t$最小割
最小割的题目：USACO 5.4.3
Dinic求最大流，loj #101
BZOJ 1717
字符串Hash做法：
每次二分一个答案，然后Hash每一个答案长度的子串，比较看有没有$k$个相同的Hash值即可.
Hash做法TLE了两个点.
后缀数组做法：
每次二分一个答案，然后在$height$数组里分组，看有没有连续$k$个相同长度的$height$即可.
poj 1947
之前不知道怎么规划状态……看了题解才知道……定义状态定义需要的就行了
设$dp(u, j)$为以$u$点为根的子树剩$j$个点的最小操作数
则初始化
$dp(u, 1)=|son \in u|(u$不是叶子)
$dp(u, 1)=0(u$是叶子)
转移简单了，$dp(u, j)=min(dp(u, j -k) + dp(v, k)-1)$
减一是因为之前$(u,v)$是断开的，把$(u,v)$连上就少一次操作
模板及讲解
推荐入门文章
分数规划就是求$\sum A_i / \sum B_i$最大/最小。
$\sum A_i / \sum B_i$最大/最小问题
我们设$C(x)$为$\sum A_i / \sum B_i \geq x$是否成立
(或者是$\sum A_i / \sum B_i \leq x$)
$\sum A_i / \sum B_i \geq x$
去分母$ \sum A_i \geq \sum B_i \times x$
移项$\sum A_i - \sum B_i \times x \geq 0$
合并同类项$\sum (A_i - B_i \times x) \geq 0$
那么我们进行二分，每次二分一个$x$，如果$C(x)=true$，那么$l=mid$，否则$r=mid$
$C(x)$的计算就是把$(A_i - B_i \times x)$排序，取最大的那几个
最优比率生成树
进行二分，每次二分一个$x$，每条边的边权设为$A_i - B_i \times x$，然后跑MST检验答案即可(根据$\sum (A_i - B_i \times x) \geq 0$)。
最优比率环
进行二分，每次二分一个$x$，每条边的边权设为$A_i - B_i \times x$，然后DFS版的SPFA检测是否存在正/负环(根据$\sum (A_i - B_i \times x) \geq 0$)
常见题型：
1、$\sum A_i / \sum B_i$最大/最小问题
Q：见解析
解：见解析
例题：poj 2976
2、最优比率生成树
Q：见解析
解：见解析
例题：poj 2728//强行Prim不想写……明年再说吧qaq
3、最优比率环
Q：见解析
解：见解析
例题：Bzoj 1960