C. George and Job 详细题解

问题描述

给定一个长度为 $n$ 的整数序列 $p_1, p_2, \dots, p_n$。需要从中选出 $k$ 个互不重叠且长度均为 $m$ 的区间

$$[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]$$

满足：

$$1 \le l_1 \le r_1 < l_2 \le r_2 < \dots < l_k \le r_k \le n $$

且 $r_i - l_i + 1 = m$。目标是最大化这些区间内所有元素的总和。

数据范围

• $1 \le (m \times k) \le n \le 5000$
• $0 \le p_i \le 10^9$

问题分析

由于区间长度固定为 $m$，且不能重叠，相当于在原序列中选出 $k$ 个长度为 $m$ 的连续子段，子段之间至少间隔一个位置（因为 $r_i < l_{i+1}$）。
这是一个典型的动态规划问题，可以用前缀和快速计算任意区间 $[j-m+1, j]$ 的和。

动态规划解法

预处理

先计算前缀和数组 $pre$，其中

$$pre[i] = \sum_{t=1}^{i} p_t, \quad pre[0] = 0$$

那么区间 $[j-m+1, j]$ 的和为

$$sum(j) = pre[j] - pre[j-m]$$

状态定义

设 $dp[i][j]$ 表示已经选择了 $i$ 个区间，且最后一个区间的右端点不超过 $j$ 时能获得的最大总和。
其中 $1 \le i \le k$，$0 \le j \le n$。

边界条件

• $dp[0][j] = 0$ 对所有 $j$（没有选任何区间，总和为 $0$）。
• 当 $j < i \cdot m$ 时，无法选出 $i$ 个不重叠的长度为 $m$ 的区间，因此 $dp[i][j] = 0$（初始化时已为 $0$）。

状态转移

对于 $dp[i][j]$，考虑位置 $j$：

• 不选以 $j$ 结尾的区间：此时最优值就是 $dp[i][j-1]$。
• 选以 $j$ 结尾的区间：该区间为 $[j-m+1, j]$，其和为 $pre[j] - pre[j-m]$。那么前 $i-1$ 个区间的右端点必须 $\le j-m$（因为不能重叠），因此这部分的最大值为 $dp[i-1][j-m]$。
  总值为 $dp[i-1][j-m] + (pre[j] - pre[j-m])$。

综上，转移方程为：

$$dp[i][j] = \max\left( dp[i][j-1],\; dp[i-1][j-m] + pre[j] - pre[j-m] \right) $$

答案

最终答案为 $dp[k][n]$，即选出 $k$ 个区间且最后一个区间右端点不超过 $n$ 的最大和。

时间复杂度与空间复杂度

• 状态数：$O(k \cdot n)$，由于 $k \le n/m$，最坏情况下 $k \approx n$，故 $O(n^2)$。当 $n=5000$ 时，$n^2 = 2.5 \times 10^7$，在可接受范围内。
• 每个状态转移 $O(1)$，总时间复杂度 $O(n \cdot k)$。
• 空间复杂度：使用二维数组 $O(k \cdot n)$，约为 $5000 \times 5000 \times 8$ 字节 $\approx 200$ MB，在内存限制内（$256$ MB）。也可以优化为滚动数组降至 $O(n)$，但本题二维直接实现即可。

示例验证

示例1

输入：

5 2 1
1 2 3 4 5

$m=2, k=1$，选择长度为 $2$ 的区间，最大和区间为 $[4,5]$ 和 $=9$，输出 $9$。

示例2

输入：

7 1 3
2 10 7 18 5 33 0

$m=1$，每个区间就是一个单点。选择最大的 $3$ 个数：$33, 18, 10$，总和 $61$，输出 $61$。

代码实现（标程）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> pre[i];
        pre[i] += pre[i - 1];   // 前缀和
    }

    // dp[i][j]: 选 i 个区间，最后一个右端点 ≤ j 的最大和
    vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, 0));

    for (int i = 1; i <= k; ++i) {
        for (int j = i * m; j <= n; ++j) {
            dp[i][j] = max(dp[i][j - 1],
                           dp[i - 1][j - m] + (pre[j] - pre[j - m]));
        }
    }

    cout << dp[k][n] << endl;
    return 0;
}

总结

本题的关键在于将问题转化为选 $k$ 个固定长度的不重叠子段，并利用前缀和快速计算子段和。动态规划的状态设计为“已选 $i$ 个区间，最后一个区间右端点不超过 $j$”，通过考虑是否以 $j$ 结尾进行转移，保证了无后效性和最优子结构。最终时间复杂度 $O(nk)$，在给定数据范围内可行。