题解：P14465 霞む夏の灯（ending）

_Communist · 2025-11-08 15:44:46 · 题解

这里 p 是题面中的 \pi。考虑 dp，我们从 1 到 n 依次确定 p，假设现在已经确定了 [1,i) 的 p，需要确定 p_i。如果 |i-p_i|<m，贡献为 c_{|i-p_i|}，否则贡献为 c_m。

一个很自然的想法是状压 (i-m,i+m) 这段区间，表示对于 j\in(i-m,i+m) 是否存在一个 p_k=j，如果存在 i 就不能再选了。这样就能解决 p_i\in(i-m,i+m) 的贡献。

对于 |i-p_i|\geq m 的部分，转移系数并不好计算，考虑延迟钦定，再加一维状态 j 表示 [1,i] 中有多少个 p_i \geq i+m，将这一部分的贡献在转移时考虑。

最终的状态定义 dp_{i,j,S} 表示考虑前 i 个 p，有 j 个 p \geq i+m，S 的含义如上文所述。状态数是 O(n^22^{2m-1}) 的，单次转移枚举 p_i 的情况 O(m)，时间复杂度 O(n^2m2^{2m-1})。

转移细节上，我们先讨论 k_i=-1。

假设从 dp_{i-1,j,S} 转移到 i，转移的时候每次需要考虑第 i+m-1 位是否要分配给前面某个 p_k\geq i-1-m 的 k，如果给的话有一个 j 的系数。然后按照 p_i 进行分类讨论：

对于 \exist k_i \not= -1 的情况，就是系数比较麻烦，这是 dirty work，代码比较恶心，实现也因人而异吧。