博客食用更佳：
https://www.cnblogs.com/czyty114/p/14987595.html
$\;$
作者自己的学习笔记，因此会不断更新

BZOJ 3864

$\;$
https://darkbzoj.tk/problem/3864
$\;$
我们的任务是统计合法$T$串的数量
发现$|S|$很小，猜到是状压，但不知道如何设计状态，如果只是用$S$表示与哪些位置匹配了似乎也很奇怪，不大可做
如果设$f_{i,j,m}$为$S[1..i]和T[1..j]$的LCS为m的方案数，再按LCS去转移。
但这样会导致算重，因为同一个$T[1..j-1]$有可能既属于$f_{i,j-1,m}$又属于$f_{i-1,j-1,m-1}$
所以划分有问题的时候，考虑多加几个条件。
想个最狠的，假如我们很nb，把LCS(1,j-1),LCS(2,j-1),…,LCS(i,j-1)都记录下来记为S，那么同一个$T[1..j-1]$就只可能属于一个S中了。
但肯定开不下来，发现LCS(i,j)和LCS(i-1,j)最多差1，于是就可以用二进制S表示差分数据去转移

正睿提高组十连测day7-C 种树

$\;$
有$n$个人，我们要把他们分成若干个队伍，第$i$个人所分到的队伍的人数数量$\leq a_i$
两种方案不同当且仅当存在原先在同一个队伍两个人被分到了不同的队伍
$n,a_i\leq 2000$

我们发现，对于同一组的人来说，限制的瓶颈在于$a_i$最小的那个人，设其为$x$
那么对于一个队伍来说，我们只需在选$x$的时候，一块选上即可
我们首先考虑将$a_i$从大到小排序，枚举$i$的时候，我们只关心前面还没选的人的数量
设$dp_{i,j}$表示前$i$个人，目前有$j$个人还没选的方案数
$$dp_{i,j}=\sum_{k=0}^i dp_{i-1,j+k-1}\times C(j+k-1,k-1)$$
直接转移是$n^3$

优化，把按人dp换成按队伍dp来做
设$dp_{i,j}$表示组好了队伍数$\geq i$，剩下$j$个人的方案数
$$dp_{i-1,j+b_{i-1}-k(i-1)} <– dp_{i,j}\times C(j+b_{i-1},k(i-1))\times \frac{k(i-1)!}{{(i-1)!}^k\times k!}$$
发现转移过程有调和级数，复杂度就是$O(n^2 log n)$

BZOJ 3594

$\;$
操作只能是一个后缀，然后把每个数的增量一定就是这种形式：000111222333555
我们要同时满足$i<j,a_i+d_i\leq a_j+d_j, l_i < l_j$，且是一个二维的前缀。
所以我们不能一层一层的去清空。
那么就维护一个二维的树状数组

四边形不等式

$\;$
对于这类dp：
$$f_j=min\{f_i+w(i,j)\}$$
$\;$
如果满足$w(i,j)+w(i+1,j+1)\leq w(i,j+1)+w(i+1,j)$
那么决策一定是满足单调性的
大概就是：将上面的柿子移项，发现对于决策$i$，$j$变到$j+1$的过程中$i$的增量较大一些
所以在j不断移动的时候，$i$就可能不是最优决策了,且决策点一定会往后走
用单调队列做可以做到$O(nlogn)$
且注意四边形不等式不能做最大值
$\;$
对于2D1D问题，即：
$f_{l,r}=min\{f_{l,k}+f_{k+1,r}+w(l,r)\}$
$\;$
如果$w$函数满足区间包含单调性且满足四边形不等式，那么$f$也满足四边形不等式
证明我不会啊，估计就咕了吧
而如果$f_{i,j}$是满足四边形不等式的，最优决策点$best_{i,j}$是单调的，即：$best_{i-1,j}\leq best_{i,j}\leq best_{i,j+1}$
时间复杂度可以看成一个矩阵上的图来分析，共有$n$条对角线，每条跨越的幅度为$n$，所以能优化成$n^2$
$$f_{i,j}=min\{f_{k,j-1}+w(k,i)\}$$
$\;$
也是同样的道理

luogu P3648 序列分割

$\;$
观察到最终的答案和分割的顺序没有关系，一个数只不会和与它在一组的数产生贡献
于是考虑从后往前分割
如果用求没有贡献的和最小的那个dp，w是满足四边形不等式的，但是那样还带一个log，过不去
考虑新的做法
即换一种dp形式：
$$dp_{i,j}=max\{dp_{k,j-1}+(s_i-s_j)\times s_j\}$$
$\;$
这个东西虽然不能用四边形不等式来做，可以考虑去斜率优化，把j先去掉，因为是相邻的两维嘛
$$dp_{i}=max\{dp_{j}+(s_i-s_j)\times s_j\}$$
$\;$
要是$dp_j+(s_i-s_j)\times s_j$最大
不妨设其为$c,s_j=x,dp_j-s_j^2=y$
$$s_ix +y=c$$
$$y=-s_ix+c $$
维护一个上凸壳就可以了

BZOJ 2131 免费馅饼

$\;$
一开始的想法是按$t$排序，是为了保证选的顺序一定是从左到右
然后推出：$2t_i-p_i\geq 2t_j-p_j (p_j\leq p_i)$
或$2t_i+p_i\geq 2t_j+p_j (p_i\leq p_j)$
然后我把这个东西成了一个二维前缀矩阵最大值问题。
发现二维树状数组内存开不下，而有两维，有因$t$已排序好了，无法去处理
考虑原始柿子：
$$2(t_i-t_j)\geq |p_i-p_j|$$
$\;$
这个绝对值非常的讨厌，但可以发现，只有上面两个柿子都满足条件才可以。（因为一交换变成负的更满足条件了）
这样就不用去讨论绝对值里面正负的问题。
从而得出：$i$在$j$后面选，当且仅当：
$$2t_i-p_i\geq 2t_j-p_j $$
且
$$2t_i+p_i\geq 2t_j+p_j $$
按一维排序，另一位树状数组维护即可
总结：推出两个东西前后选，必须满足什么条件，排序就能消去一维，有些绝对值符号，看看一种情况能否包含另一种（即满足这一种就一定满足那一种），就可以去掉了