题解：P17859 「GLR-R5」白露 / ros

P2441M · 2026-11-08 19:31:24 · 题解

做死我了。

考虑每次往序列末尾添加一个数 x，那么 x 是合法的当且仅当所有前面出现的 >x 的数都与 x 相邻。

设 L_x 表示 <x 的与 x 相邻的数构成的集合，R_x 表示 >x 的与 x 相邻的数构成的集合。

不妨先考虑记录最大值 v：令 f_v 表示最大值为 v 的合法序列个数。考虑添加一个数 x 后，如何得到最大值为 v 的合法序列。若添加的是 v，则贡献显然是 \sum\limits_{i=1}^vf_i；否则若添加的是 x\in L_v，则原序列最大值为 v，但是这里只保证 x\in L_v 不足以保证 x 合法。

这启发我们再去记录 g_{v,x} 表示最大值为 v、x 可以添加到序列末尾的序列个数。由于 x\in L_v，所以状态个数显然是 \mathcal{O}(n) 级别的。

这样很容易就能得到 f 的转移：

再来考虑 g 的转移。若原序列最大值为 v，则添加 v 或者 x 显然都不影响 x 的合法性。若添加满足 x<t<u 的数 t，则 x,t 都与 u 相邻，加入 t 后 x 必然不合法。若添加满足 t<x 的数 t，那么我们保证 t 可以被添加到末尾即可。

但是这里又出现了新的需要记录合法性的量。那咋办？

考虑先计算出 \sum\limits_{t<x\land t\in L_v}g_{v,t}，但是这样会多算 x 不能添加到末尾的序列。

做一个重要的观察：若 x\in L_v 且 x 不能添加到末尾，则 <x 的可以被添加到末尾的数至多只有一个。这是因为，考虑 x 不合法说明存在 x<y<v 使得 x,y 不相邻，那么 <x 的合法的数必须同时与 y,v 相邻，显然至多只有一个。

这启发我们再去记录 h_{v,x} 表示最大值为 v、x 不能添加到序列末尾，但存在 t<x 能添加到序列末尾的序列个数。

这样我们直接减去 h_{v,x} 就能扣掉多算的部分了。原序列最大值为 v 的贡献就是 2g_{v,x}+\sum\limits_{t<x\land t\in L_v}g_{v,t}-h_{v,x}。

再来考虑原序列最大值为 u<v 的情况。此时我们保证 x 在原序列中合法即可。显然 u\leq x 的序列必然合法，而若 x<u<v 则要有 u\in R_x，贡献 g_{u,x}。

这样我们就得到了 g 的完整转移

再来考虑 h 的转移。还是先考虑原序列最大值为 v 的情况。添加 v,t 都是合法的，若添加一个满足 x<p<v 的数 p 显然会使 t 变得不合法。而若原本 x 合法，则为了让它变得不合法必然会令 t<x 也变得不合法。因此贡献恰好就是 2h_{v,x}。

再来考虑原序列最大值为 u<v 的情况。显然要有 u>x，否则 x 不可能变得不合法，同时 t 要在原序列中合法。由此得到 h 的完整转移：

至此我们终于得到了所有 DP 转移。

暴力做上述转移的时间复杂度为 \mathcal{O}(n^2m)，需要优化。