题解：P9506 [BalkanOI 2018] Homecoming

CX_xiaoli · 2026-08-07 16:14:32 · 题解

本人把上面所有题解都食用了一遍，还是有地方没看懂，在写代码的时候也遇到一些细节问题，所以写了这篇题解总结。如果你看前面题解有没搞懂的地方，希望这篇题解对你有帮助。

题目大意

有 n 个课程，每个课程价值为 a_i，但是要得到价值需要购买第 i 本及其之后的 k-1 本课本，课本呈环形排布。问最大价值。

环形 DP 通解

因为课本呈环形排布，所以这题是一道环形 DP。对于环形 DP，有以下两种常见解法：

如这道题，我们通过预设某些前提使得环状的特性不被触发（如那题中的强制不从第一天晚上睡到第二天早上）跑一遍 DP，再将这些前提反过来使得环状的特性被触发，再跑一遍 DP。适用于能够找到区分用到环的性质和不用到环的性质的题。
如这道题，我们通过暴力枚举答案数组的最前几项和最后几项，判断环状条件被满足后再统计答案。适用于每个数据的范围都很小的题。

考虑这题数据范围很大，所以果断使用第一种解法。

分析状态转移

我们发现，本题的环形特性就是如果靠前的教材被购买了，那么靠后的课程就有部分教材不用重复购买（因为环的存在，靠后的课程有可能需要购买靠前的教材）。那我们就可以从这个点下手：我们先假设靠后的课程转到前面去的那部分教材也需要购买。对于样例就是第 3 个课程需要购买第 3 本和第 1 本教材才能获得 a_3 的收益。那么我如果要上第 i 门课程，到底需要买哪些课本呢？我们发现，如果在之前上过了第 i-1 门课程，那么第 i 到第 i+k-2 这 k-1 本教材就已经被购买（假设没有超出第 n 本课本），我们只需要购买第 i+k-1 本教材。所以我们设 dp_i 为前 i 门课程，第 i 门课程必须学，得到的最大价值，那么有在选第 i-1 门教材时的状态转移方程：

dp_i=dp_{i-1}+a_i-b_{i+k-1}

读者可能会问：那前面已经购买了第 i 门课程的 i-2、i-3、……、1 本课本的情况是不是都要分别转移？那不就 O(n^2) 了吗？其实不然。根据贪心，如果前面我们学习第 x 门课，只购买了第 y 门课程的 i-2 本课本，那么如下图所示，可以找到课程 z 完美地身处 x 和 y 之间，完全白嫖课本。所以如果状态转移时不从 dp_{i-1} 处转移，也就是用来转移的课程 j 与当前课程 i 之间隔了至少一门课，那么他们之间就至少隔了 k 门课程，不然就可以存在有上面所说的白嫖情况，但是这种转移并没有统计到，不优。

想到这里，我们不妨考虑从哪一个 j 转移是最优的。首先，如果不从 i-1 课程转移，显然有下面的状态转移方程：

dp_i=dp_j+a_i-(b_i+b_{i+1}+\cdots+b_{i+k-1})

而 a_i-(b_i+b_{i+1}+\cdots+b_{i+k-1}) 的值是固定的，所以当且仅当 dp_j 最大时，转移得到的 dp_i 最大。再结合上面所说的第一种情况，我们得出了总的状态转移方程：

dp_i=\max\{dp_{i-1}+a_i-b_{i+k-1},\max_{j=1}^{i-2}dp_j+a_i-\sum_{j=i}^{i+k-1}b_j\}

其中 b 数组的下标按 \bmod n 理解，即转到前面去的教材也要购买。

考虑环的影响

别忘了，这是个环形 DP。我们只是考虑了转到前面去的教材也要购买的情况，还有不需要购买的情况没考虑呢！

首先我们发现，转到前面去的教材（不妨称作大于 n 的教材）也要购买，等价于第 1 门课程没学。只有这种情况，大于 n 的教材才有买的意义。于是这道题分为两个 DP：

强制学习第 1 门课程，此时大于 n 的教材不用买，因为学了第 1 门课程，第 1 到第 k 本教材肯定已经买了。此时的边界： dp_1=a_i-\sum_{j=1}^{k}b_i
同时如果上面状态转移方程中 b 的下标大于 n 则不加进答案。
强制不学习第 1 门课程，此时大于 n 的教材需要购买，只要按上面的方程转移即可。此时的边界： dp_1=-\infty
因为不能选嘛，所以不能从 dp_1 转移，赋成负无穷就行了。

最后的答案就是每次 DP 时所有状态的最大值。说了这么多，终于可以写代码了。

优化与细节

此时的代码是 O(n^2) 的。为了优化时间复杂度，我们对 b 数组做前缀和，并且在状态转移过程中对 dp 数组做前缀最大值。前缀和很简单，前缀最大值有一些细节。令 mx_i=\max_{j=1}^{i}dp_j
那么第一种情况（强制学习第 1 门课程）时边界为
mx_0=-\infty,mx_1=dp_1
因为必须上第一门课，所以不能从 dp_0 转移，设为负无穷。第二种情况（强制不学习第 1 门课程）边界为
mx_0=mx_1=0
注意 mx_1=0 而不是 mx_1=dp_1=-\infty，因为虽然不选第 1 门课，但是从第一门课转移是合法且收益为 0 的。
交互题传的指针参数经常越界 RE，所以在使用之前先把内容取出放到数组里。注意要给 b 数组破环为链，数组大小要开两倍。
开 long long。交互题不能使用 #define int long long，不然 solve 函数传参也都变成 long long 了，由于 C++ 的函数重载机制，交互库识别不到函数就会 CE。

代码实现

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

const int N = 4e6+5;
const long long inf = 0x3f3f3f3f3f3f3f3f;
long long a[N], b[N], dp[N], mx[N], sum[N];

long long solve(int n, int k, int *A, int *B)
{
    for (int i = n; i > 0; i--) {
        a[i] = A[i - 1];
        b[i] = B[i - 1];
    }
    for (int i = 1; i < n; i++) {   // 破环为链
        b[i + n] = b[i];
    }
    for (int i = 1; i < 2 * n; i++) {
        sum[i] = sum[i - 1] + b[i];
    }

    mx[0] = -inf;
    mx[1] = dp[1] = a[1] - sum[k];  // 强制选第一个课
    for (int i = 2; i <= n; i++) {
        if (i + k - 1 <= n) {
            dp[i] = max(dp[i - 1] + a[i] - b[i + k - 1], mx[i - 2] + a[i] - sum[i + k - 1] + sum[i - 1]);
        } else {
            dp[i] = max(dp[i - 1] + a[i], mx[i - 2] + a[i] - sum[n] + sum[i - 1]);  // n以后的选第一个课的时候就买过了
        }
        mx[i] = max(mx[i - 1], dp[i]);
    }
    long long ans = max(0ll, mx[n]);

    mx[0] = mx[1] = 0;
    dp[1] = -inf;   // 强制不选第一个课
    for (int i = 2; i <= n; i++) {
        dp[i] = max(dp[i - 1] + a[i] - b[i + k - 1], mx[i - 2] + a[i] - sum[i + k - 1] + sum[i - 1]);
        mx[i] = max(mx[i - 1], dp[i]);
    }
    ans = max(ans, mx[n]);

    return ans;
}

AC 记录，完结撒花！如果你觉得这篇题解很详细，或者对你有帮助，那就点个免费的赞吧！

管理员大大求过！