题解 「EZEC-11」雪的魔法

· · 题解

通过线性规划对偶，我们将原问题转化为：

给 [l,r] 中每一个位置一个权值 w_i，使得所有长度不超过 m 的区间的 w_i 之和不超过 1，最大化 \sum\limits_{i=l}^ra_iw_i。

容易发现最优解中 w_i 的值不会小于 -1。

题目进一步转化为：在 [l,r] 中选若干个数求和，若两个相邻的被选择的数 a_x,a_y(x<y) 满足 y-x<m，则需要在区间 (x,y) 中选择一个数减去，最大化最终得到的值。

容易得到一个时间复杂度为 O(nq) 的做法：

int n,m,q,a[N];
ll f[N],dp[N];
signed main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    while(q--){
        int l=read(),r=read();
        ll w=0;
        f[l-1]=0;
        for(int i=l;i<=r;i++){
            if(i>=l+m)w=max(w,dp[i-m]);
            w=max(w,f[i-1]-a[i]),dp[i]=w+a[i],f[i]=max(f[i-1],dp[i]);
        }
        printf("%lld\n",f[r]);
    }
    return 0;
}

代码中 dp_i 表示选择的最后一个数是 a_i 的最优答案，f_i 表示 [l,i] 这段区间的最优答案。

我们对于原序列分段，每段长度为 m，共 \lceil\frac{n}{m}\rceil 段，若 m>\sqrt n，段数为 O(\sqrt n)，对于每一段的左/右端点，我们向右/左跑一遍上面的 dp，预处理出每个端点开始的 f，这里的时间复杂度为 O(n\sqrt n)。

以下 Case 均在初始 m>\sqrt n 的情况下讨论。

Case1：在最优解中，存在相邻两个被选择的数之间的距离小于 m 且不在同一个段中或存在相邻两个被选择的数不在相邻的两个段中。

与预处理 f 类似的，预处理 g，g_i 表示从端点开始到 i，开头先减去一个数或不选前 m-1 个数的最优答案。枚举每个整段，设当前段为 [L_1,R_1]，下一段为 [L_2,R_2]，若在 [L_1,R_1] 中没有数被选择，则答案被包含在 g_{R_1,l}+f_{L_2,r} 中，即答案不大于 g_{R_1,l}+f_{L_2,r}，若存在相邻的两个被选择的数分别在 [L_1,R_1] 和 [L_2,R_2] 中，则答案为 \max\{f_{R_1,l}+g_{L_2,r},g_{R_1,l}+f_{L_2,r}\}，这一部分的时间复杂度为 O((n+q)\sqrt n)。

Case2：

我们将分段后的序列排成一个矩阵，矩阵的每行为一个整块，即每行 m 个元素，共 \lceil\frac{n}{m}\rceil 行，记矩阵的第 i 行第 j 列为 (i,j)，(i,j) 对应原序列的第 (i-1)\times m+j 个位置，我们认为 (1,1) 处于矩阵的左上角。

若最优答案不在 Case1 中，那么对于相邻两个被选择的数，它们在矩阵上的位置一定是后一个数在前一个数的右下方向，每行至少有一个数被选择，将所有被选择的数依次连成一条折线。

Case2.1：\lceil\frac{n}{m}\rceil<m。

我们在矩阵中间划一条竖线，它将每行分为长度为 \lfloor\frac{m}{2}\rfloor,\lceil\frac{m}{2}\rceil 的两段，将第 i 行的后一段与第 i+1 行的前一段拼接，又能得到若干个长度为 m 的段，我们再次套用 Case1 的解法，相当于解决了折线越过我们所划的竖线的情况。

接下来需要解决折线不越过竖线的情况，那么如果在折线一边选了数，另一边就不能选数，在解决竖线一侧的问题时，另一侧的数完全无用，可以认为是 n 变为了原来的一半，此时 m 是否变为原来的一半没有影响。

若将一侧的元素顺次拼接，得到一个长度为原来的一半的序列，并认为 m 也随着矩阵宽度变化为原来的一半，解决一侧的问题相当于解决规模更小的原问题。

于是我们得到了两个规模更小的与原问题题意一致的子问题，n,m 均为原来的一半。若一个询问的最优解选择的第一个数与 l 或选择的最后一个数与 r 不在竖线的一侧，这种情况在之前套用 Case1 算法的时候已经计算过了，不需要递归，因此每个询问至多只会被递归到一个子问题中。

这一部分的时间复杂度为 Case1 的时间复杂度，即为 O((n+q)\sqrt n)。

Case2.2：m\le\lceil\frac{n}{m}\rceil。

我们取出矩阵中间的一行，这一行中至少有一个数被选择，枚举这一行的每个位置，钦定一个位置被选择，若一个询问的区间与这一行有交，那么就能计算出这个询问的答案。

与 Case2.1 类似，我们得到了两个规模更小的与原问题题意一致的子问题，n 为原来的一半，而 m 不变。显然每个询问至多只会被递归到一个子问题中。

这一部分的时间复杂度为 O((n+q)m)，由于 m\le\lceil\frac{n}{m}\rceil，时间复杂度为 O((n+q)\sqrt n)。

注意：只有 Case2.1 的算法与 Case2.2 的算法交替使用才能得到正确的时间复杂度。

对于整个算法：

预处理部分复杂度为 T(n)=O(n\sqrt n)+2T(\frac{n}{2})，T(n)=O(n\sqrt n)。

此外对于每次询问产生的复杂度为 T(n)=O(\sqrt n)+T(\frac{n}{2})，T(n)=O(\sqrt n)。

总时间复杂度为 O((n+q)\sqrt n)。

若在一开始 m\le\sqrt n，我们略微修改 Case2.2 的算法，在序列中间设置一个断点，枚举与断点距离小于 m 的 2m-1 个位置，钦定一个位置被选择，显然这些数不可能都不被选择，否则一定可以找到更优解。这样就可以通过多次递归使得 m 变为 \sqrt n 级别。注意这里并不需要保证相邻两个被选择的数在矩阵上的位置一定是后一个数在前一个数的右下方向，仅仅是通过这个算法缩小 n 的规模。

这一部分的时间复杂度为 T(n)=O(nm)+2T(\frac{n}{2})，当 m>\sqrt n 时，递归停止，所以其中 O(nm) 不超过 O(n\sqrt n)，T(n)=O(n\sqrt n)。询问部分的复杂度分析与之前询问部分的复杂度分析同理。

至此，我们在 O((n+q)\sqrt n) 的时间复杂度内解决了本题，实现精细即可做到 O(n+q) 空间复杂度。

另：通过一些操作可以把问题转化为每个长度为 m 的区间最多选择一个数，求选择的数的和的最大值。这个问题也可以使用上面的算法解决，常数较小。