dp

AGC031B

本质是，先缩点，然后相同的颜色可做划分，划分的区间不能有重叠。

将 $i$ 不划入集合 与 将 $i$ 和上一个 $b_i$ 出现的位置划入一个集合，由于合并的性质，直接从上一个 $b_i$ 出现的位置转移即可。

或者将每一个 $b_i$ 出现的前一个位置求个 $sum$，各从这些位置转移也行。

AGC046B

$f_{i,j}$ 代表已经填完 $i$ 行 $j$ 列的方案数，枚举上一步是填的行还是列，但是会有一些重复的情况，重复的情况其实就是在 $(i-1,j-1)$ 的基础上，第 $i$ 行的前 $j-1$ 个和第 $j$ 行的前 $i - 1$ 个各有一个被填了，那就是 $f_{i,j} = f_{i - 1 , j} \times j + f_{i , j - 1} \times i - f_{i - 1 , j - 1} \times (i-1) \times (j - 1)$。

AGC060A

存在子区间某东西出现次数大于一半，意味着存在 $aa$ 或者 $aba$ 的结构。

直接对着这个设计状态 $dp$ 即可。

ABC118D

dp 记录某个火柴数的最大长度，最大最高位，后继状态，就行了。

ABC142E

简单状压 dp。

ARC157C

把 $x^2$ 拆开，做差分，即 $(x+1)^2 - x^2 = 2x + 1$。

所以把一次方的和存下来转移即可。

ABC159F

看完就会 $O(n^2S)$ 的 dp 了，就是卡左右端点，算中间的部分背包的方案数，然后乘上 $l \times (n-r+1)$。

魔改这个背包，$f_r$ 代表以 $r$ 为右端点的满足题意的 $\sum l$ 是多少。

答案就是 $\sum f_r \times (n - r + 1)$。