区间dp
1.石子合并
区间dp n3方
随 i 增加 k 单调不降 优化成 n2
2. cf1025D
gcd 预处理出来
n4 f[i][j][k] 区间 i j 以 k 为跟的二叉树是否存在
n3 f[i][j][0/1]表示区间 i j 根节点在左端还是右端 转移变成 o1
g[i][j][0/1] 区间 i j 根节点为 i/j 的二叉树是否存在 枚举k 与 j 互质 ，则可以作为根 转移复杂度 O(n)
二叉树的一个中序遍历对应一个区间
3. 多重背包
O(nvk)
单调队列优化
f[i][j] = f[i-1][j-k*v]+w;
k*v 相当于一条链 在 %v 意义下 v+p 2*v+p 3*v+p 是相同的
能转移过来的状态相当于一个区间 随k增加 区间移动
4.整数划分问题
划分一个数(有序)的方案数
设 f[i][j] 表示 i 个数拼成了 j 的方案数
添加一个值为 1 的数 ：f[i][j]->f[i+1][j+1] 所有数+1 ：f[i][j]->f[i][j+i] O(n2)
优化 ： 大于 根n 的数最多有 根n 个 钦定 dp 数组中的数全部大于 根n 第一个转移变成了每次添加一个值为 根n 的数 f[i][j]->f[i+1][j+根n] 第一维 根n O(n sqrt(n));
小于 根n 的数完全背包一下
枚举有多少个数大于 根n : 假设 k 个，拼成 L F[k][L] * f[n-L] F 第一维用前缀和优化一下 f 是 < 根n 的数的方案数
根号分块思想 >根n 和 <根n 两种方法做
5. 树形dp
HAOI 树上染色
设 i 为根的子树 选了 k 个点 无法转移 不知道染色点选在哪里
枚举每条边 统计每条边的贡献 f[u][k] 枚举在一个子树选了j个黑点 剩 k-j 个黑点
转移的时候像树形背包合并
写树形背包时要小心 不要把复杂度写假
Code：
6.状压DP
枚举超集
枚举子集
例题 HNOI 公交线路
f[i][s]表示i的后 p 站停靠的状态是 s
矩乘 把 f[i] 看做一个行向量 构造一个矩阵A 使得 f[i]*A = f[i+1]
矩阵乘法满足结合律 可用矩阵快速幂 O(k3*log(n)) 当 f[i]仅有f[i-1]转移过来 就可以构造一个矩阵来优化DP了
外层状态矩乘优化掉
内层预处理出有用状态 ： 始终包含 k 个 1 的状态是有用的
7.概率期望
加法原理
乘法原理
期望的线性性
SHOI 2014 概率充电器
因为一个节点带电：u 带电 或者 相邻的边带电 ， "或者" 不好做，考虑u不带电,并且相邻边不带电 就很好做了
设 f[u] 表示 u 的子树，u 不带电的概率
没有考虑 father 的影响
所以 dp 两遍 这时根节点的答案是正确的
考虑子节点的答案可以由 father 节点转移过来
以v作为根，把发father节点看做根(换根法) father的答案直接除掉当前子树的答案 ， 子节点答案再乘上father节点答案
8. DP优化
决策单调性优化 （打表 / yy）
有决策单调性当且仅当满足四边形不等式
维护每一段的左端点，右端点，决策点是什么 放到队列里面 按左端点排序
加入一个 k，比较k和这一段的左端点，如果左端点都劣于k，则踢掉，不然在段里二分，找到最优位置，分成两段，前一段是之前的，后一段是新加入的决策点
例题： 诗人小G
斜率优化
例题： 玩具装箱 （决策单调性 / 斜率优化） 加强版 ： k次方只能决策单调性
奇技淫巧
1. WQS二分
https://blog.csdn.net/chenxiaoran666/article/details/83381779 WQS二分学习笔记
如果答案关于某个变量 x 是凸函数 要求某个f(x) 但是不好求，但 max f(x)的值很好求 于是可以减掉一个函数， 使答案向要求的位置逼近
凸函数减掉切线，切点处取最大值
因为斜率单调 所以可以二分斜率
例题 ： CF739E
n<=200
f[i][a][b]表示抓了 i 个宝贝 用了 a 个宝贝 b 个超级球
枚举怎么抓第 i 个容易转移
n<=100000
如果确定了 a 关于 b 是一个凸函数
二分套二分
O(nlog2n)
杂题
1.绝世好题
2. sit
n个座位的圆桌， k个人去坐 ， 任意时刻联通块个数 <= G 求方案数
设 f[i][j] 表示坐了 i 个人 有 j 个联通块的方案数
先做人 然后把空格插到人中间
分三种情况讨论
经典题
1. 求 n 个点有标号连通图的数量
总方案 - 不合法
枚举一号点所在联通块的大小
2.
把不认识的两个人连上边， 二分图染色
每个联通块有黑色数，白色数
每个联通块黑白染色，做背包，使得黑白差尽量小
3.
