经典例题
摆渡车
设fi表示i这个时刻发车最小答案，枚举上一次发车的时间j，容易转移
但这是O(t^2)
考虑优化
1.斜率优化
2.发现n,m<t，设计fi这种状态很浪费
优化1：若两次发车间隔>2m,完全可以再发一辆车，于是复杂度O(tm)
优化2：若某次发车之前的m个时刻内都没有人，这个点是废点，只会用作优化1，于是直接fi=fi-m转移
最终复杂度O(T+n*m^2)
3.更改dp状态
gi,j表示运走了前i个人，第i个人的等待时间为j
则ti + j就是第i个人接走的发车时间
考虑分段的经典思路：i和i-1是否同一辆车
简单转移
其中不在同一辆车可以前缀min优化
复杂度O(nm)
是否还可以继续优化？
考虑对人做分段
而不是对时间分段
考虑每次发车，要不就是在有人来的时间点发车，或者上一个人发车结束后紧接着发车
预处理后一种情况，枚举上一个发车的点
复杂度O(min{nn,nm})
dp=观察性质+搜索+状态优化+转移优化
树形DP
道路
设fu,i,j表示u到根，i条L边，j条R边未被指定
枚举左右儿子指定哪条边即可
答案是f[1][0][0]
初始化所有叶子
树上染色
对每条边算贡献
树上背包
数位DP
需要记录是否顶着上界，是否处于前导0
发现dfs可以很好的解决这个问题
windy数
板子
花神的数论题
Beautiful numbers