动态规划
标签（空格:动态规划
状态设计
1，状态设计->拆分or合并
2，利用二分减少状态
3，状态分段
例题
Bzoj 2298
解：每个人的话相当于排名([a_{i}+1,n-b_{i}]),如果两个人的话代表的区间
有心爱那个键但不完全重合，那个这两个人冲突
那么就变成了选择最多不想交线段<->
Bzoj 1190
解：质量大的背包，观察数据性质考虑->吧状态数值变小，
对于b相同的数据分组dp，对于每一组分别转移，态数值变小
Cover ：
给定n个点无根树，节点i权值为(w_i)，若选择i，则可以将距离这个点(w_i)以内的点全部覆盖，任意一边的长度为1
问：最少选多少点能将整棵树覆盖(（n<=100）)
数位DP
sdoi 201
3 淘金
Bzoj 3329
x xor (x<<1+x)=(x<<1)->
(x<<1) + x = x xor (x<<1);
问题转化为一个数的二进制形式中没有相邻的1
"^"->不进位加法
期望，概率dp
1，求一些限制条件下的概率期望
2，求概率常常为正推，期望常常为逆推
3，有拓扑序问题直接Dp，没有拓扑问题高斯消元是常见法
4，期望可加
5，全概率公式，贝叶斯公式
dp of dp
给出一个n*n的棋盘，上面有一些格子必须是黑色的，其他可以染黑或染白，求有多少种染色方法使得棋盘上的最大白色正方形边长为k
dp of dp
斯坦拿树
Bzoj 3205
预处理每个地方向每个方向推动到达哪里
令f[l][r][x][y]表示在点（x，y）将编号在[l,r]区间内放入机器人全部合并最小推动次数
推动：。。。。
利用<斯坦拿树>用途（spfa）跑最短路进行转移
斜率优化：
方程类似f[i]=min(f[j]+a[i]+b[j]+c[i]d[j]+e)
去掉常数和只与i相关的变量
f[i]=min(c[i]d[j]+(d[i]+b[j]))
与直线方程b=kx+y
最大/最小化截距
这样的点一定在凸壳上
维护凸壳在凸壳上找到最优决策
凸函数优化
IOI 2016 Alien
1<>将对角线以下的点翻到对角线以上
除去被包含的点，剩余的点按照x从小到大排序，y一定也是从小到大的
，且一个正方形会覆盖连续一断点
令f[i][j]表示用了i个正方形，覆盖了前j个点的最小总面积
转移枚举最后一个正方形覆盖的是哪一段点
f[i][j]=min{(f[i-1][k]+y_i-x_k+1)^2-max(0,y_k,x_{k+1}+1)^2)}
斜率优化->用栈维护，复杂度O(nk),60%;
2<>若不限制选取的小正方形的个数，而是改为每多选取一个小正方形就需要额外的C的面积
g(j)表示覆盖钱j个点的最小面积
g(j)=min{f[k][j]+kC}
g(j)=min{(g（k)+(y_j-x_{k+1}+1)^2-max(0,y_k-x_{k+1}+1)^2+C)}
g(n)可以用斜率优化在限行时间内求出，并可以同时求出此时最少需要的最小正方形数
通过g（n）求出对应的f[x][n]的值
杂题选讲
int main() {
using namespace std;
return null;
}
TC SRM563-950
考虑两个格子之间的关系，如果两个硬币在这两个格子上，是否有机会调出
->记忆化搜索两个格子
TC SRM564-850
对于前面的b随便取，最有一个b一定能调整使得异或和为n
然而有(A_i)的限制
将(A_i)排序，对于最大的元素(A_1)，考虑(B_1)在(A_1)的最高位的二进制是否取1
(/....................................................................../)
Bzoj 3080
枚举边权总和->枚举平均数->计算生成树每条边对方差的贡献->完
NEERC 2017-2018 Moscow