$\;$
作者自己的学习笔记，因此会不断更新
UPD：T1-T13 7.25 9:58

博客食用更佳
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 $$
按一维排序，另一位树状数组维护即可
总结：推出两个东西前后选，必须满足什么条件，排序就能消去一维，有些绝对值符号，看看一种情况能否包含另一种（即满足这一种就一定满足那一种），就可以去掉了

放置街灯

$\;$
$n^2$做法直接树形背包解决
考虑线性做法
因为题目同时给了两个条件，要在第一个条件最小化的情况下，最大化第二个条件。
不妨对第二个条件做个补集转化。
现在相当要让两个条件整体最小化，但第一个条件的优先级更高。
不妨选进制$k>n$，那么把选法压缩成一个$k$进制数就可以了。

luogu P5504 柠檬

$\;$
考虑只能从颜色相同的位置转移，且一定会选这种颜色。
否则一定可以将区间两段同时缩进，得到一种不劣的方案。
发现，这玩意是满足四边形不等式的，因为平方，$i$越小，增长的速度越快。
按理说，这东西的决策点应该是单调递减的。
但有可能新加入的决策非常的优，导致决策点又往右横跳。
维护一个单调栈存储决策点的信息，每次$x$入栈时看栈顶被次顶干掉的时间如果比栈顶干掉$x$的时间早，栈顶肯定就没用了。
然后转移$i$时，要时刻注意栈顶是否已经是不优了

CF1509C

$\;$
从前往后扫的过程中，只会关心当前最小值和最大值，看作是两个指针，它们一定会不断的往下和上扩展，导致极差变大。
那我们肯定是让它往上或往下扩一个值。
所以考虑区间dp
$$dp_{l,r}=min(dp_{l+1,r},dp_{l,r-1})+s_r-s_l$$
$\;$
$s$要提前排序，复杂度：$O(n^2)$

CF441E

$\;$
直接去求最小距离不大现实，最多做到$n^2$
显然可以二分，变成判定问题。
接第$i$个订单的人肯定要停留在$x_i$，所以只需记另外一个人的位置，记为$j$
那么设$dp_{i,j}$表示接了前$i$个订单，另一个人停在了$j$的位置是否可行
转移：看是哪个人接了$i+1$订单，$->dp_{i+1,j}$或$dp_{i+1,i}$
显然对于$|x_{i+1}-x_j|>mid$，显然这样的$j$挂掉了，而发现，如果按坐标排序，这相当于弹出首尾两段的一些状态。
而如果$|x_{i+1}-x_i|\leq mid$，就要加入$x_i$这个状态。
所以我们需要维护一个有序序列，支持删除和插入，$set$是最好的选择
$O(nlogn\times log w)$ $w$为值域

CF1096E

$\;$
显然，我们会先去枚举1的分数，然后再枚举有多少人和他同分。
剩下的问题就是有$i$个人，分数和为$s$，分数都不超过$m$的方案数
对于这种分数都不超过某个值，很难去搞，如果只是简单的枚举，复杂度又太高。
不妨我们去容斥，看有多少个人超过了这个值。
那么先塞给这些人$m+1$的分数再说，然后剩余的分数随便分配就好了

AGC016F

$\;$
博弈论dp
对于多个有向图博弈问题
$sg(s)=sg(s_1)\;xor\;sg(s_2)\;xor… xor\;sg(s_m)$

现在要让先手必胜，即$sg(s)>0$,所以$sg(1)\neq sg(2)$
将其分层，一一确定每个点的sg值
我们按照从小到大的顺序，枚举$S$的子集$T$，对于$x\in T$，令$sg(x)=0$
那么剩余的部分$G$，$G$中的每一个点，都要向$T$中连至少一条边，反过来是随便连。
那么不断分层分层，在dp的过程中保证1和2在同一层即可

ICPC2018 Gem Island

$\;$
考虑总方案数是$n(n+1)..(n+d-1)$
对于每一种分配方案，我们想知道他的方案数有多少
首先勒令分裂的宝石的主人是谁，在这个基础上方案数已有$\frac{d!}{\prod a_i}$
但注意到这里我们只关心哪天晚上分裂的主人是谁，而并没有关心是哪一颗宝石
所以发现对于同一个人，后面宝石数会不断增加，还要乘上个$a_i !$，那么就消去了
所以方案数一定是$d!$
$\;$

经典dp方式

$\;$
搭楼梯
在考虑贡献的时候，正常思维应该是竖向考虑，考虑前$r$的和
不妨去横向考虑,对于每个$x$，设$b_x$为$a_i\geq x$ 的数量
那么$x$的贡献是$min(b_x,r)$
在dp的时候，我们也要这么横向考虑
因为知道$\sum_{i=1}^n a_i=d$
设$f_{i,j}$表示前$i$的高度，已经搭了$j$个格子的方案数。
转移时，看一下最高层搭了多少个格子
显然这里$a_i$并不是严格不增的（只不过我们考虑的时候这样方便一些）
而且这样我们也能很方便的知道，此时$a_i\geq x$有多少个了