dp 优化——lca

[AGC017F] Zigzag

给定一个 $N$ 层的三角形图，第 $i$ 层有 $i$ 个节点。第 $i$ 层的节点，从左到右依次标号为 $(i, 1), (i, 2), \ldots , (i, i)$ （具体如上图所示）。你需要从 $(1, 1)$ 往下画 $M$ 条折线。对于每条折线的每一个小段，你可以从 $(i, j)$ 画到 $(i + 1, j)$ 或者 $(i + 1, j + 1)$ 。同时你还必须保证第 $i$ 条折线的任何一个位置必须不能处在第 $i - 1$ 条折线的左侧，它们必须按照从左到右的顺序排列。有 $K$ 条限制，每条限制形如 $(A_i, B_i, C_i)$ 。表示第 $A_i$ 条折线处于位置 $(B_i, j)$ 时，下一小段必须走向 $(B_i + 1, j + C_i)$ ，也就是当 $C_i = 0$ 时向左，当 $C_i = 1$ 时向右。询问不同的折线画法的方案数，对 ${10}^9 + 7$ 取模。 $1 \le N, M \le 20$ ， $0 \le K \le M (N - 1)$ 。其它变量在合理范围内。 $1\ \leq\ N\ \leq\ 20$ $1\ \leq\ M\ \leq\ 20$ $0\ \leq\ K\ \leq\ (N-1)M$ $1\ \leq\ A_i\ \leq\ M$ $1\ \leq\ B_i\ \leq\ N-1$ $C_i\ =\ 0,1$

从上往下 $\rm dp$ 是很困难的，因为你无法区分仍在一个点的折线。

考虑一条一条折线的轮廓线 $\rm dp$ ，你只需要记录上一条折线。

但是你发现你只知道上一条折线的下半部分并没有办法确定上一条折线，所以需要在中断点记录偏移量。

这太困难了，并且带三个 $N$ 过不了。

但是其实你没必要关心上一条折线，你只需要关心上条折线对当前折线的限制。

你发现这个“限制”是一条折线，你只需要关心限制的形状即可，所以无需多记一维，每次向右走就把后面第一个 $1$ 删掉现在向右，向左需要保证限制这一位是 $0$ ，然后限制不变。

[ARC108E] Random IS

从左到右排列了 $N$ 张椅子，第 $i$ 张的编号为 $a_i$ （保证 $a_i$ 互不相同）。

$\texttt{Snuke}$ 想要标记一些椅子并把剩下的丢掉，一开始所有椅子都没有被标记。我们称一种标记方案是好的，当且仅当其标号递增。即，若标记的编号为 $i_1<i_2<\cdots<i_k$ ，则有 $a_{i_1}<a_{i_2}<\cdots<a_{i_k}$ 。

$\texttt{Snuke}$ 将重复一下操作来标记椅子：

称 $x$ 是不错的当且仅当把 $x$ 加入后标记方案仍是好的，记其数量为 $k$ ；

若 $k=0$ 结束操作，否则均匀随机选择一个标记并继续操作 $1$ ；

求最终标记个数的期望。

$n\le 2000$ 。

考虑 $f_{l,r}$ 表示某个方案中 $[l,r]$ 这个区间中最先选的是 $a_l,a_r$ ，区间期望个数。

$f_{l,r}\gets\frac 1k\sum_{p\in(l,r)}[a_l<a_p<a_r](f_{l,p}+f_{p,r})$

正常转移顺序就自然保证了 $p\in(l,r)$ ，每个 $l$ 维护一个数据结构求 $(a_l,a_r)$ 中 $f_{l,p}$ 的和， $r$ 同理。

P9338 [JOISC 2023 Day3] Chorus

给定一个长为 $2n$ 的序列，每个元素是左括号或右括号，左右括号数量相等，每次你可以交换相邻元素，问至少交换几次能使原序列可以被划分为 $k$ 个左括号都在右括号前的合法括号子序列。

$n\le 10^6$ 。

首先将原序列的左括号上、右括号右图画出来。

考虑一个贪心判定：选前面极长的一段左括号，然后匹配最靠前的几个右括号。

首先不可能选更长的了，其次选更短的没有这个优，所以这个贪心是对的。

在网格图上就是每次尽可能向上走，再向右碰到对角线。

我们把每个顶到上轮廓的点尽可能往左移动，就变成了要在轮廓线上选 $k$ 个点，使得它们可以覆盖对角线。

对“对角线被覆盖的进度”进行 $\rm dp$ ，考虑分成 $k$ 段的分段 $\rm dp$ ，把我们钦定的这种方案画出来，轮廓线下面的图形与原序列轮廓线上面的图形的交的面积就是逆序对的个数，也就是我们要求的交换次数。

根据四边形不等式的性质，将其两维偏导后如果矩阵的正负性相同，那么其满足四边形不等式，而这里贡献形式刚好也是面积，所以自然满足四边形不等式。

可以 wqs 二分 + 二分决策点队列解决，但是 $\log^2$ 。

把式子写出来， $w(l,r)=\sum_{i=l+1}^r \max(r-sum_i,0)$ ， $sum_i$ 表示第 $i$ 个右括号的高度（前面有多少左括号）。

但是这样并不方便优化，对着左括号这一维 $\rm dp$ ： $w(l,r)=\sum_{i=l+1}^r\max(sum_i-l,0)$ ， $sum$ 表示第 $i$ 的左括号的宽度（前面有多少右括号），这样转移就跟左端点有密切联系了。

接下来我们就可以对每个 $l$ 二分出最小的 $p$ 使得 $sum_{p+1}\ge l$ ，转移变成 $w(l,r)=\sum_{i=p_l+1}^r(sum_i-l)=S_r-S_{p_l}-(r-p_l)l$ 。

斜率优化即可，至于要限制 $r\le p_l$ 这件事情，我们可以用单调队列维护满足这样的 $l$ 的最小 $f_l$ ，然后在 $p_l$ 处加入凸包，由于 $p$ 是单增的，所以不会有什么问题。

更进一步地，我们可以更加简化这个问题，你发现 $p_l>r$ 的时候这个贡献竟然是正的，所以我们可以把延迟加入改为立即加入。

斜率优化也可以单调队列线性维护，所以单 $\log$ 。

其实我们没必要维护后面那个单调队列，直接在 $p_l$ 处加入凸包，多往后转移几个总是不劣的。

关于 wqs 二分的注意事项：如果你使用整数二分，那么你需要关心数值相等时要取数量的 $\max$ 还是 $\min$ ，根据这个来调整大了取等还是小了取等，具体来说如果你取数量的 $\max$ ，那么本来是正确答案的答案会向更大的方向偏移一段，所以我们应该大了取等。

省事的做法是加入凸包时仅仅弹掉斜率严格不优的点，求的时候求所有转移后相等的段数的 $\max$ ，也就是单调队列弹掉的时候也要更新答案。

注意这里并不能用“二分到左边或者右边的端点都可以”来糊弄过去，如果答案会向右偏，但你偏偏小于的时候取等，那么你二分出的斜率是差 $1$ 的。

再次需要注意的是，由于我们更改了转移（尽可能远），所以我们要找的不是划分成 $k$ 段，而是 $\le k$ 段的最小答案（强行抬升段数可能变劣），其实只需要特判一开始就合法的情况。