dp

· · 个人记录

AGC031B

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

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

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

AGC046B

--- 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)$。