任务太多，只能粗略写了，挑重点写了。
石子合并 f[i][j]与f[i][k]，f[k+1][j]有关，搞搞就好。
凸多边形划分 把n边形化成n-2个三角形所产生的贡献和最大，f[i][j]代表i与j连了一条边，从点i到j的贡献，然后枚举一个中间点k，这样就构成一个三角形并划分子问题了。
删回文串 把字符串一直删回文，删成空串的最短步骤，其实不用考虑整个回文串，因为中间可以删去，所以对于区间f[i][j]表示删掉区间i,j的最短步骤，如果该区间头尾相同，就可以用f[i+1][j-1]更新了，或者像后面那种情况，不然就说明整串不能直接删去，所以就把f[i][j]分成f[i][k]和f[k+1][j]就可以了。
01背包
完全背包
多重背包 当物品个数为a，重量为w，价值为v，把它划分成2^0+2^1+2^2+…+零头x个（总和为a），重量为w×2^i，价值为v×2^i，把它们当成01跑，这样就会组成0~a所有数。
树的直径 两个BFS贪心或DP都行
行列状压
集合状压
状压+最短路 NOIp2016愤怒的小鸟
状压+玄学 NOIp2017宝藏
状压+背包 1~n中任选k个使乘起来得到的数x，不含质数的平方因子。稍微分析一下，也就是质数因子最多只有1个，因为对于数n来讲，大于sqrt(n)的质因子只有1个，设为x，x相同的数只能选一个，小于sqrt(n)的质数只有8个，按其的选取情况搞个状压，对于不同的x，背包一下，OK？
直接分块
大力分块 把块排序，二分，就可以搞搞区间小于某数的个数。
块状链表 可支持插入删除等，也就是当每块大于步长时就暴力裂开，反正不会太多的。
差分约束系统
SPFA+DP NOIp2017逛公园
NOI1 求1~m中选1个数x，使x经过给定位运算操作后的值最大。 位与位之间独立，从高位往低位，试填01，看最后结果是1并且在1~m的范围内，就可以了。
NOI2 在矩阵中，从左上走到右下的路径，所经过的值，排序后，字典序最小的路径几何？ 每找到最小值，就把矩形分成四部分，左下及右上的部分舍去，明明可以开个二维数组，但此题空间卡得紧，所以优化，因为删掉矩形后，剩下的合法范围，对于每行来讲是一个区间，维护每行的合法范围，就不用搞个二维数组了。
子树问题 Dfs(u) { low[u]=++tim; ti[u]=tim; for Dfs(u->v); high[u]=tim; }
欧拉序1 Dfs(u) { print(u); for Dfs(u->v); print(u); } 跟普通Dfs序差不多，相同数字的1头1尾中间是它子树
欧拉序2 Dfs(u) { print(u); for Dfs(u->v),print(u); } 可用于求LCA(x,y)，序列第1个x位置与y的位置的区间中，深度最小的就是x,y的lca
DFS离线统 用于离线解决树上的1些问题，看似普通，实则功能强大。对于最开始搜索到结点u时，我们可以动态保留点到根的路径信息，等到u遍历完它的子树时，若能把信息做1个差分，就可以得到子树的信息，把信息映射到DFS序上或桶上，也就是可以记录1个数组的信息，再用1些数据结构维护，就可以解决很多问题了。
比如1：1颗有根树，树上每个结点有个颜色/深度，问每个结点到根的路径中/子树中，与其颜色相同/深度=x的结点的个数。（NOIp2016天天爱跑步）（比树剖强啊）
比如2：每个点p在两颗有根树t1,t2上都有1个对应的位置，每次询问x,y，问有多少个点，在t1中是x的子树，在t2中在根到y的路径上。（NOI阿狸的打字机）
比如3：1颗有根树，有一些链将其覆盖，询问两点间是否有链将其覆盖，即p1的子树中与p2的子树有没有链的2个端点。（CF983E）
在数轴上给出1些线段，从中挑选，使线段互不相交，最多能选出多少？ 在数轴上给出1些线段，从中选1些点，使每个线段都至少包含1个点，点最少多少？ 在数轴上给出1些线段，互不相交的线段可分为1组，请问最少能分成几组？（前缀和亦可）
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：开学阶段学习总结”