前：day4下午——动态规划

衢州

本质：

背包

T1

sol

SRM 625

f[i][j]前i个人坐完了，有j个联通块。新来一个人。情况：新加一个联通块。或者任意坐在任意一个联通块的旁边。坐完后，把两个联通块并在一起。桌子标号->乘n。

bzoj 2287

先做一遍背包，f[i]体积为i，g[i]不用x的方案数。
0~wx-1，f[i] = g[i]
i>=wx：g[i] - f[i] - g[i-wx]

多项式 除 单项式 ：
单项式，x^wi+1
多项式：01背包

T4 BZOJ 2287

prefer序列：
性质：和树一一对应，长度N-2。
编号在n-2~n的无根树有n^{n-2}个。

所以可以转化为和书没有关系的问题。

T5 bzoj 4753

在树上选一个联通块。
dfs序上dp。f[i][j]前i个，选了j个人。

T6 SRM 613

题意：给一个棋盘放一些棋子。每列最多放一个，每行所有<=L[i]的列，最多放一个，所有>=R[i]的列最多放一个。
题解

ppt的题解

T7 SRM 648

https://blog.csdn.net/codedream4/article/details/43733249

数位DP

T8 SRM 522 Level 3

判断一个01串是否合法，相邻两个1不合法。

枚举每一位，这一位是1的总数多少，
f[i][j][k]，填了i位，上位是j，k

CF 908 G

https://www.zgz233.xyz/2018/06/05/codeforces-908g/

状压dp

dp[s][i]经过s的点，最后一个点是i

bzoj 3864

Games on DAG

https://blog.csdn.net/worldwide_d/article/details/79327924

带容斥dp

UOJ #37

https://blog.csdn.net/zrl000308/article/details/52107997

h[s]有多少本质不同图的个数，2^|e|
f[s]合法的强联通图的个数。
f[s] = h[s] - 不联通。

DAG：把所有初度为0的点删去，还是DAG。

缩成墙连通分量。
2^(S-T,T)

二项式反演
斯特林反演
莫比乌斯反演