F2. Pictures with Kittens (hard version) - 题解

哈喵~！各位热爱算法的小伙伴们，大家好呀！咱是乃爱算法的猫娘，今天又要和大家一起攻略一道有趣的题目啦！这道题是关于可爱的...小猫咪！呜喵~ 看到小猫咪就充满了干劲呢！准备好和我一起分析这道题了吗？Let's go!

比赛与标签

比赛: Codeforces Round 521 (Div. 3) 标签: data structures, dp 难度: *2100

题目大意喵~

简单来说，就是我们有一个由 n 张小猫图片组成的序列，每张图片都有一个“美貌值” a_i。我们需要从中挑选恰好 x 张图片进行“转发”。

但是有两个重要的规则需要遵守哦：

转发数量: 必须正好转发 x 张图片，不多不少。
覆盖规则: 在原始的图片序列中，任何长度至少为 k 的连续片段，都必须至少包含一张我们转发过的图片。

我们的目标是，在满足这两个规则的前提下，让转发的所有图片的美貌值总和达到最大！如果无法做到，就要告诉程序酱 "-1" 哦。

举个栗子：如果 k=2，就意味着每两张相邻的图片（比如第 i 张和第 i+1 张）里，我们至少要转发一张。

解题思路喵！

这道题要求最优解（最大美貌值），而且决策之间相互关联（选了这张会影响下一张能选哪里），这种感觉... 没错了，是 动态规划 (Dynamic Programming) 的味道，喵~

1. DP状态的定义

首先，我们要确定 DP 的状态是什么。我们需要知道：我们已经考虑了多少张图片？已经转发了多少张？最后一次转发的是哪一张？

所以，一个很自然的想法是定义 dp[i][j] 表示：已经转发了 i 张图片，并且第 i 张转发的图片是原序列中的第 j 张时，所能获得的最大美貌值总和。

2. 状态转移方程

想一想，如果我们决定要转发第 j 张图片作为我们转发的第 i 张，那么第 i-1 张转发的图片（假设是第 p 张）必须满足什么条件呢？

根据题目的“覆盖规则”，如果第 p 张和第 j 张是连续两次转发，那么它们之间的所有长度为 k 的区间都必须被覆盖。这意味着 p 和 j 的距离不能太远。具体来说，从 p+1 开始的长度为 k 的区间 [p+1, p+k] 必须要有一次转发。因为我们假设 j 是 p 之后的第一次转发，所以 j 必须在这个区间里，也就是 p+1 <= j <= p+k。

反过来推，就是 j-k <= p <= j-1。

所以，要计算 dp[i][j]，我们需要找到一个合适的 p（j-k <= p < j），使得 dp[i-1][p] 最大。状态转移方程就出来啦：

dp[i][j] = a[j] + max(dp[i-1][p]) 其中 max(0, j-k) <= p < j （这里的 a[j] 是第 j 张图片的美貌值，下标从 0 开始）

3. 朴素DP的瓶颈

如果我们直接按照这个方程来计算，会有三层循环：

第一层循环 i 从 1 到 x（转发次数）
第二层循环 j 从 1 到 n（当前图片）
第三层循环 p 从 j-k 到 j-1（寻找之前的最优决策点）

总的时间复杂度是 O(x * n * k)。对于这道题 n, k, x <= 5000 的数据范围，5000^3 肯定会超时的说！必须要想办法优化！

4. 滑动窗口优化！

我们来仔细观察一下 max(dp[i-1][p]) 这一部分。当我们在计算 dp[i][j] 时，j 是不断向右移动的（j=1, 2, 3, ...），而 p 的取值范围 [j-k, j-1] 也在同步向右滑动。

这不就是一个经典的 滑动窗口求最值 的问题嘛！喵哈哈，咱最喜欢这个了！解决这个问题最好的工具就是 单调队列 (Monotonic Queue)！

我们可以用一个 deque（双端队列）来维护一个下标 p 的序列。这个队列有以下特点：

队列中的 p 对应的 dp[i-1][p] 值是单调递减的。
队列头部的元素是当前滑动窗口内的最优决策点。

当我们要计算 dp[i][j] 时：

移除过期元素: 检查队头的 p 是否已经小于 j-k。如果是，说明它已经不在当前的窗口内了，就从队头把它 pop 掉。
取最优值: 此时队头的元素就是 [j-k, j-1] 范围内的最优决策点 p_best。我们就可以用 dp[i-1][p_best] 来计算 dp[i][j] 了。
维护单调性: 在把当前的 j-1（作为下一次计算的 p）入队之前，先从队尾开始，把所有 dp[i-1] 值比 dp[i-1][j-1] 小的元素都 pop 掉，这样才能保证队列的单调性。然后再把 j-1 从队尾 push 进去。

通过单调队列优化，寻找 max(dp[i-1][p]) 的时间从 O(k) 降到了均摊 O(1)。总的时间复杂度就变成了 O(x * n)，这个复杂度就可以愉快地通过啦！

5. 空间优化

还有一个小细节，我们计算 dp[i] 这一层时，其实只依赖于 dp[i-1] 这一层的数据。所以我们不需要一个 x * n 的二维数组，只需要两个一维数组 dp_prev 和 dp_curr 来回滚动就行了，空间复杂度就从 O(x * n) 优化到了 O(n)。

6. 最终答案

当我们完成了所有 x 次转发的计算后，最终的答案是什么呢？最后一次（第 x 次）转发的图片位置 j 也有限制。为了保证 j 之后不再有长度为 k 的空档，j 必须满足 n - j < k，也就是 j > n - k。所以，最终答案就是 max(dp[x][j])，其中 j 的范围是 [n-k+1, n]。

如果最后算出来的最大值还是一个非常小的负数（我们初始化的值），那就说明没有合法的方案，输出 -1 就可以啦！

代码实现の说

下面就是加上了猫娘注释的AC代码啦，希望能帮助你理解每一步都在做什么哦~

cpp

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>

using namespace std;

// 定义一个非常小的数作为负无穷，用来初始化DP数组，表示某个状态不可达
const long long NEG_INF = -1e18;

int main() {
    // 关闭同步流，让输入输出更快一点喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, x;
    cin >> n >> k >> x;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 使用滚动数组进行空间优化
    // dp_prev 存储上一次转发（repost-1次）的结果
    // dp_curr 存储当前次转发（repost次）的结果
    vector<long long> dp_prev(n + 1, NEG_INF);
    // 初始状态：转发0次，在位置0之前，美貌值为0（这是一个虚拟的起点）
    dp_prev[0] = 0;

    // 外层循环：枚举转发的次数，从1到x
    for (int repost = 1; repost <= x; repost++) {
        vector<long long> dp_curr(n + 1, NEG_INF);
        // 单调队列，存储的是上一次转发的位置p
        // 队列中p对应的dp_prev[p]是单调递减的
        deque<int> dq;

        // 内层循环：枚举当前转发的图片位置i
        for (int i = 1; i <= n; i++) {
            // 滑动窗口的左边界
            int L = max(0, i - k);

            // 1. 移除队头过期的元素
            // 如果队头的p已经小于窗口左边界L，就说明它太远了，不能作为上一次转发的位置
            while (!dq.empty() && dq.front() < L) {
                dq.pop_front();
            }

            // 2. 维护队列的单调性
            // 在把 i-1 (作为下一次的p) 入队之前，
            // 先从队尾把所有 dp_prev 值比 dp_prev[i-1] 小的p都移除
            // 注意：这里要先处理 i-1 的入队，再计算 dp_curr[i]
            // 但是为了代码简洁，我们可以先计算，再把 i-1 入队，逻辑上是一样的
            // 这里代码的逻辑是：先准备好 i-1，再计算 i
            
            // 稍等，代码的逻辑是先处理i-1，然后计算i
            // 当我们计算dp_curr[i]时，需要的是dp_prev[p]在[i-k, i-1]范围内的最大值
            // 所以在循环到i时，我们需要把i-1加入到单调队列中
            // 这里的 dp_prev[i-1] 是指转发到第 i-1 张图片时的最大美貌值
            if (dp_prev[i-1] != NEG_INF) { // 只有可达的状态才入队
                while (!dq.empty() && dp_prev[dq.back()] <= dp_prev[i-1]) {
                    dq.pop_back();
                }
                dq.push_back(i - 1);
            }
            
            // 3. 计算状态转移
            // 队头 dq.front() 就是当前窗口 [i-k, i-1] 内的最优决策点p
            if (!dq.empty() && dp_prev[dq.front()] != NEG_INF) {
                dp_curr[i] = a[i - 1] + dp_prev[dq.front()];
            }
        }
        
        // 滚动数组，用当前轮的结果覆盖上一轮的结果，为下一次转发做准备
        dp_prev = dp_curr;
    }

    // 寻找最终答案
    long long ans = NEG_INF;
    // 最后一次转发的位置 i 必须在 [n-k+1, n] 之间，才能保证末尾不会有长度为k的空档
    for (int i = n - k + 1; i <= n; i++) {
        if (dp_prev[i] > ans) {
            ans = dp_prev[i];
        }
    }

    // 如果ans还是初始的负无穷（或小于0），说明无解
    if (ans < 0) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

复杂度分析だにゃ

时间复杂度: O(x * n) 的说。我们有两层主循环，外层是转发次数 x，内层是图片数量 n。在内层循环中，每个图片位置 i 都只会被 push 进单调队列一次，pop 出一次。所以单调队列的操作均摊下来是 O(1)。因此总的时间复杂度就是 O(x * n)。
空间复杂度: O(n) 的说。我们使用了滚动数组的技巧，所以只需要两个大小为 n+1 的 vector 来存储DP状态，以及一个大小最多为 k 的 deque。所以空间复杂度是 O(n)。

知识点与总结喵~

这道题是一道非常经典的 DP + 单调队列优化 的题目，解决这类问题的关键步骤是：

正确建模: 建立一个能够描述问题状态的 DP 数组，比如本题的 dp[i][j]。
写出转移方程: 根据题意推导出状态之间的转移关系。
发现优化点: 观察转移方程，如果发现它是在一个固定大小的滑动窗口内求最值，就要立刻想到单调队列！
实现优化: 使用 deque 实现单调队列，将 O(k) 的查找优化到均摊 O(1)。
考虑边界: 注意初始状态的设置和最终答案的统计范围，比如本题中最后一次转发的位置限制。

掌握了单调队列优化 DP 的技巧，很多看起来很棘手的难题都会变得清晰起来哦！希望这篇题解能帮到你，也希望你能从解决小猫咪的问题中获得快乐和成就感！继续加油，你一定可以成为更厉害的算法大师的，喵~！

F2. Pictures with Kittens (hard version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

1. DP状态的定义 ​

2. 状态转移方程 ​

3. 朴素DP的瓶颈 ​

4. 滑动窗口优化！ ​

5. 空间优化 ​

6. 最终答案 ​

代码实现の说 ​

复杂度分析だにゃ ​

知识点与总结喵~ ​