题解：AT_arc153_e [ARC153E] Deque Minimization

· · 题解

\text{Link}

有意思呢。

思路

首先思考对于确定的 X，如何得到 f(X)。贪心考虑如果当前字符小于等于串的开头就放到开头，否则放到结尾，正确性不难证明。

考虑区间 DP，定义 f_{l,r} 为在某个时刻选出的串为 Y_{l,r} 的方案数。初值为 f_{i,i}=1。

转移式：

f_{l,r}\to f_{l-1,r} \quad (Y_{l-1}\le Y_l)\\ f_{l,r}\to f_{l,r+1} \quad (Y_{r+1}>Y_l)

我们按照 l 为行，r 为列把转移画出来。所有框起来的点都可以网上走。答案是对走到 Ans 的路径计数。

这个网格图的形式是，保留前面一段不降的，然后第 i 行会在右边第一个 Y_j>Y_i 的地方停下来。

你把右边的边界描出来，发现只会变化 |\Sigma| 次。

把所有右边界相同的弄到一起做，从下往上转移即可，是网格图所以转移直接插板法。贡献的组合数容易拆成卷积。注意还要加上左边三角形新增的那些点的贡献。

时间复杂度 O(|\Sigma|n \log n)。