poj 3417
题意：一棵有$N$个点的树，再往里面加入$M$条新边，现在要破坏其中的两条边，要求一条是原来树中的边，一条是新边，然后使图不连通，求方案的数量。
发现加的新边会使树产生环。观察可得一条新边$(x,y)$如果在树上$(u,v)$路径都加一，那么最后如果想使图不连通，则只能删边权为0,1的点，对于边权为0的边能删$m$次，而边权为1的边只能删1次。

BZOJ 1799
题意：给出$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。
设$dp(a,i,j)$为前$a$位数字和为$i$，数模上数字和值为$j$的个数。
枚举数字和，然后求即可。转移方程

$$
dp(a,i,j)+=dp(a-1,i+p,(j+p)\% mod)
$$

其中$mod$为枚举的数字和，$p$为$a$位上枚举填的数。

Bzoj 1026
题意：不含前导零且相邻两个数字之差至少为$2$的正整数被称为windy数。 在$A$和$B$之间，包括$A$和$B$，总共有多少个windy数？
数位DP模板。设$dp(i, pre)$为第$i$位前面的值为$pre$的windy数的个数。
然后一般数位DP用记忆化完成。所以记忆化。基本思想是试填法。
具体实现看代码，其中的限制意思是本位上不能填完所有的数，例如最大数字为41002，如果首位填了4，后面第二位只能填0、1，若后面第二位填了1，则后面第三位只能填0。如果第二位填了0，则后面第三位可以填$[0,9]$中任意数字。以此类推。

Codeforces 1073E
题意：给你一个范围$[l,r]$，求其中数字数位上最多有$k$个不同的数的和。
这个数位DP如果求个数就比较容易，但是这里求和就比较麻烦。
先考虑求个数，设$dp(i,st)$为前$i$位的数的集合$st$的个数。注意前导零转移即可。
如果要求和，那么填完数对每个数位都要求一下对答案贡献。即如果填了第一位，那么后面填的可行个数将就是第一位上的填数贡献次数。以此类推。具体实现看代码。

poj 1734
给定一个无向图，求出节点数至少为$3$的最小环。输出方案

当Floyd中最外层循环到$k$，$dis(i,j)$则代表不经过大于等于$k$编号节点的最短路。

所以最小环我们可以枚举必过某个点的最小环是多少。即考虑过$k$点最小环，且只由不大于等于$k$编号节点的点组成。那么最小环即为

$$
\min_{1 \leq i < j < k}(dis(i,j)+a(i,k)+a(k,j))
$$

由于对称性，所以不会影响结果。
输出方案即根据DP转移来回溯答案。具体看代码实现。

BZOJ 2200
题意：无向图中求$S$出发到每个点的最短路。并且有一些单向边，如果有一条单向边可以从$A_i$到$B_i$，那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

显然最短路模板，但是有负权图并且卡 SPFA。
所以我们利用

如果有一条单向边可以从$A_i$到$B_i$，那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

发现这些有向边将无向图分成了几个联通块，即不加入这些有向边，原图为几个连通块。
所以我们将联通块缩点，然后就成了 DAG 上的最短路，然后拓扑序来求即可。

具体实现看代码。

Hdu 2196
题意：给出一棵带边权树，求出每个点的到最远点的距离。

显然的一道无根树DP，所以先DP求一次最远点，然后再看怎么转移。
记$maxd(u)$为以$u$为根子树中的节点到根的最远点的距离。
这里有一种非常麻烦的情况就是父亲的题目所求答案的这条最长链就在这个分支中。那么我们只能选取一条其他分支的最大答案进行更新。
设$dp(u,0/1)$为以$u$为根到$u$点的最远点的距离。直接转移即可。

树直径做法：因为每个点到某个直径端点距离最远，所以求出直径端点再搜一次即可。

CH 5A01 (简化版)
Bzoj 2726 (斜率优化版)
题意：见上。
很容易想出二维DP，即$dp(i,j)$表示前$i$个任务分了$j$个的最小值。
本题没有限制分多少份，所以第二维我们想一想是不是不必要的？
删去第二维我们就不能之前前面执行了多少次$S$，那么就算不出来，所以这里有一种方法是将费用提前计算。
设$dp(i)$表示前$i$个任务最小值。
则
$$
dp(i)=\min(dp(j)+\sum_{k=1}^i T_k \times \sum_{k=j+1}^i C_k + S \times \sum_{k=j+1}^n C_k)
$$
注意到后面的$S \times \sum_{k=j+1}^n C_k)$，这个就是将费用提前计算了，因为选择了这样的方式必然会对后面的任务产生这样的贡献，所以可以提前计算。

然后式子显然能斜率优化。但是斜率不单增，在凸壳中二分即可。则Bzoj 2726可解。

poj 1737
题意：给定$n$，求出$n$个点无向连通有标号图的个数

显然设$dp(i)$为$i$个点的无向连通有标号图的个数。
但是并不好直接算出来，所以我们可以先算不连通的，那么相当于求的图是至少有两个连通块。
然后我们通过$1$所在的连通分量来划分，即对当前的$dp(i)$, 枚举$1$所在的连通分量的节点个数$j$，显然有 $C^{j-1}_{i-1}$ 种情况。然后另外$i-j$个点任意构成无向图。所以最后的答案

$$
dp(i)=2^{\frac{i(i-1)}{2}} - \sum_{j=1}^{i-1}dp(j) \times C^{j-1}_{i-1} \times 2^{\frac{(i-j)(i-j+1)}{2}}
$$

转移即可。

Codeforces 559C
题意：给定一个$H \cdot W$的棋盘，棋盘上只有$N$个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。

刚开始想到本题就是求出过黑点的方案，然后用总方案减一下就好。
所以设出了$f(i)$表示前$i$个黑点中途一定走到黑点的方案，因此为了转移的方便，我们将点按$x,y$增序排序。方便起见，将$(1,1),(h,w)$加入黑点。
然后转移发现并不好转移。。然后我就设出答案的一个函数$g(i)=C^{x_i-1}_{x_i+y_i-2} - f(i)$表示前$i$个黑点中途一定不走到黑点的方案。

然后对于$f(i)$的转移就可以是$f(i)=g(j) \cdot C^{\Delta x}_{\Delta x+\Delta y}$

然后可以将两个函数合并成一个函数

$$
dp(i)=C^{x_i-1}_{x_i+y_i-2} - dp(j) \cdot C^{\Delta x}_{\Delta x+\Delta y}
$$

然后转移即可。答案为$dp(n)$