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

这里 $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，代码比较恶心，实现也因人而异吧。