P8182 「EZEC-11」雪的魔法

· · 题解

线性规划对偶，变成给每个位置赋 -1,0,1 权，使得任意长度 \le m 区间和 \le 1，然后最大化带权和。这个限制换句话说，就是任意距离 < m 的相邻 1 之间要有恰好一个 -1。

把序列在相邻且距离 \ge m 的 1 处劈开，则劈出来每一段里去掉 0 之后都是 1,-1 交替的形式。通过手玩，或者直接注意到这就是 n=m 的情况，我们发现这样的一段的最大权值是 a_1+\sum_{i \ge 2}\max(0,a_i-a_{i-1})。

考虑这样劈出来的段长啥样：最优解里，第一段一定以序列开头为开头，最后一段一定以序列结尾为结尾，剩下的每相邻两段距离一定恰好是 m。把所有除了第一段以外的的左端点取出来，则一个左端点的贡献可以推出来是 b_i=a_i-\sum_{j=0}^{m-1}\max(0,a_{i-j}-a_{i-j-1})。

问题变为：在 [l+m,r] 选取若干个点，每个点有点权 b，选的任意两个点距离至少为 m，最大化点权和。容易写出 DP，f(i) 从 f(i-m) 和 f(i-1) 转移过来，复杂度 O(nq)。

考虑建一张图，i 向 (i+1) 和 (i+m) 连边，则它应该几乎是一张网格图：

（图片来自 P9040 洛谷题解）我们要在这样的图上多次询问两点最长路。这是可以分治做的。

具体地，我们每次选择网格较长的一边劈开，然后对于分界线上每个点，处理经过它的最短路。因为较短的边长是根号的，主定理一下可以发现总复杂度 O((n+q) \sqrt n)。注意这里除了网格边以外还有 (2,3) 这样的斜着的边，这只会在我们第一次对行分治时有贡献，特殊处理一下即可。