课程与教材优化问题 - 算法详解

一、问题重述

有 $N$ 门课程和 $N$ 本教材，编号均为 $0$ 到 $N-1$：

• 通过课程 $i$ 可获得 $A_i$ 美元收益

• 目标是最大化净利润（收益 − 教材成本）

二、核心算法思想

2.1 环形数组展开 由于课程和教材编号是循环的（模 $N$），代码将数组展开为两倍长度：

for (int i = 1; i <= n; i++) {
    a[i + n] = a[i];
    b[i + n] = b[i];
}

这样将环形问题转化为线性问题，便于处理跨越边界的情况。

2.2 前缀和预处理

for (int i = 1; i <= 2 * n; i++) {
    sum[i] = sum[i - 1] + b[i];
}

用于快速计算任意区间教材的总成本。

2.3 动态规划状态设计

定义两个数组：

• $\text{dp}[i]$：考虑前 $i$ 门课程，且必须选择课程 $i$ 时的最大利润
• $\text{mx}[i]$：前 $i-1$ 门课程中 $\text{dp}$ 的最大值

三、算法执行过程

3.1 第一种情况：从课程 1 开始考虑

dp[1] = a[1] - boto(1, k);
mx[1] = -1e18;

• 选择课程 1，需要购买教材 1 到 $k$，计算初始利润

递推公式：

// 当 i+k-1 不超过 n 时
dp[i] = max(dp[i-1] - b[i+k-1], mx[i-1] - boto(i, i+k-1)) + a[i]

// 当 i+k-1 超过 n 时（跨越边界）
dp[i] = max(dp[i-1], mx[i-1] - boto(i, n)) + a[i]

转移逻辑解释：

1. $\text{dp}[i-1] - b[i+k-1] + a[i]$：延续选择课程 $i-1$，只需额外购买教材 $i+k-1$
2. $\text{mx}[i-1] - \text{boto}(i, i+k-1) + a[i]$：从之前的某个最优状态重新开始，购买完整区间教材

3.2 第二种情况：从课程 2 开始考虑

dp[1] = -1e18;  // 不选择课程 1
mx[1] = 0;      // 起始状态为 0

这种处理确保我们可以从任意位置开始选择课程序列。

3.3 最终答案

for (int i = 1; i <= n; i++) {
    ans = max(ans, dp[i]);
}

取所有可能结束位置的最大值。

四、关键辅助函数

long long boto(int l, int r) {
    return sum[r] - sum[l - 1];
}

快速计算教材区间 $[l, r]$ 的总成本。

五、算法复杂度分析

5.1 时间复杂度

• 数组展开：$O(n)$
• 前缀和计算：$O(n)$
• 动态规划递推：$O(n)$
• 总时间复杂度：$O(n)$

5.2 空间复杂度

• 存储展开数组：$O(n)$
• 前缀和数组：$O(n)$
• DP 数组：$O(n)$
• 总空间复杂度：$O(n)$

六、算法正确性证明

6.1 环形处理正确性 通过将环形数组展开为两倍长度的线性数组，确保了所有可能的教材区间都能正确计算。

6.2 状态转移正确性 $\text{dp}[i]$ 的定义确保：

1. 必须选择课程 $i$
2. 考虑了所有可能的前驱状态
3. 正确处理了教材购买的成本计算

6.3 边界处理正确性

• 第一种情况：允许选择课程 1
• 第二种情况：不允许选择课程 1
• 两种情况的组合覆盖了所有可能的起始位置

七、算法特点

7.1 巧妙的状态设计 将问题分解为"必须选择当前课程"的子问题，简化了状态转移。

7.2 高效的转移计算 通过前缀和优化，将区间求和复杂度从 $O(k)$ 降为 $O(1)$。

7.3 完备的情况覆盖 通过两次 DP 运行，确保了所有可能的起始位置都被考虑。

7.4 线性复杂度 $O(n)$ 的复杂度适合处理大规模数据（$n \le 2\times 10^6$）。

八、样例验证

样例输入： $n=3, k=2$ $A = [40, 80, 100]$ $B = [140, 0, 20]$

计算过程：

1. 展开数组（略）
2. 计算前缀和
3. 执行 DP：
   • 选择课程 0：利润 $= 40 - (140+0) = -100$
   • 选择课程 1：利润 $= 80 - (0+20) = 60$
   • 选择课程 2：利润 $= 100 - (20+140) = -60$
4. 最大利润为 $60$，与样例输出一致

九、总结

该解法通过：

1. 环形展开：将循环问题转化为线性问题
2. 前缀和优化：快速计算区间成本
3. 动态规划：系统性地寻找最优选择序列
4. 两次运行：确保所有起始位置都被考虑

成功在 $O(n)$ 时间内解决了这个复杂的优化问题，体现了高效算法设计的思想。