Moe's CF Life

Appearance

F1. Animal Observation (easy version) - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 620 (Div. 2) 标签: data structures, dp 难度: *2300

题目大意喵~ ​

主人，你好呀！这道题是说，我们要在 n 天里，用两台相机（一红一蓝）去拍摄野生动物，喵~ 森林被分成了 m 个区域。

相机的放置规则是这样的说：

  1. 在奇数天（第1、3、5...天），我们会放置红色相机，它会连续拍摄 2 天（也就是当天和第二天）。
  2. 在偶数天（第2、4、6...天），我们会放置蓝色相机，它也会连续拍摄 2 天。
  3. 如果相机是在第 n 天放置的，那它就只拍第 n 天这一天啦。
  4. 每台相机都能覆盖连续的 k 个区域。比如，我们可以选择让它覆盖 [j, j+k-1] 这个区间。

我们的目标是最大化能观察到的动物总数。但是要注意一点哦：如果在同一天，两台相机都拍到了同一个区域，那里的动物只能算一次，不能重复计算的！

输入会给我们 n, m, k 和一个 n x m 的矩阵，表示每天每个区域能看到的动物数量。我们需要输出一个数字，就是能观察到的动物总数的最大值，喵~

解题思路喵~ ​

这道题有天数 n，有位置 m，要求最优解，一看就是动态规划（DP）的拿手好戏啦，喵！

1. 定义DP状态 ​

我们可以定义一个DP状态 dp[i][j]，表示考虑到第 i 天的相机放置，且这台相机放在了以 j 为起始的区域（即 [j, j+k-1]），此时能获得的最大动物总数。

这里的“考虑到第 i 天”指的是，我们已经为第1天、第2天、...、第 i 天都安排好了相机的位置。

2. 状态转移方程 ​

要计算 dp[i][j]，我们需要知道第 i-1 天的相机放在哪里最好。假设第 i-1 天的相机放在了以 x 为起点的区域。

dp[i][j] 的值由两部分组成：

  • 当前放置的收益: 第 i 天放置的相机，会拍摄第 i 天和第 i+1 天。它在区域 [j, j+k-1] 能拍到的动物总数。
  • 之前状态的收益: 来自 dp[i-1][x] 的最大值。

但是，别忘了重叠部分！第 i-1 天的相机（放在 x）会拍第 i-1 和第 i 天。第 i 天的相机（放在 j）会拍第 i 和第 i+1 天。它们在第 i 天的拍摄范围可能会重叠！

所以，完整的转移方程是： dp[i][j] = (当前放置在j的收益) + dp[i-1][x] - (在第i天，位置x和j的重叠区域收益)

为了找到最优的 x，我们需要遍历所有可能的 x： dp[i][j] = (当前收益) + max_{x} (dp[i-1][x] - 重叠收益)

3. 朴素DP的瓶颈 ​

如果对每个 (i, j)，我们都去遍历所有可能的 x（从 1到 m-k+1），那么复杂度会是 O(n * m * m)。对于 m 高达 2*10^4 的数据，这肯定会超时的说！必须要想办法优化才行，喵！

4. 优化！优化！ ​

优化的关键在于处理 max_{x} (dp[i-1][x] - 重叠收益) 这一部分。我们可以根据 x 和 j 的相对位置来分类讨论，喵~

重叠区域只取决于 x 和 j 的相对位置。

  • 情况一：x 和 j 的区间完全不重叠

    • 当 x + k - 1 < j (即 x <= j - k)，x 在 j 的左边很远。
    • 当 j + k - 1 < x (即 x >= j + k)，x 在 j 的右边很远。 在这两种情况下，重叠收益为0！转移方程就简化为：
    • dp[i][j] = (当前收益) + max(dp[i-1][x]) 这个 max(dp[i-1][x]) 我们可以预处理呀！
      • 对于所有 x <= j-k 的情况，我们可以用一个前缀最大值数组 left_max[j-k] 来O(1)得到。
      • 对于所有 x >= j+k 的情况，我们可以用一个后缀最大值数组 right_max[j+k] 来O(1)得到。

  • 情况二：x 和 j 的区间有重叠

    • 这发生在 j - k < x < j + k 的时候。
    • x 的取值范围长度大约是 2k。因为 easy version 里的 k 非常小（k <= 20），所以我们可以直接暴力枚举这 2k-1 个可能的 x，并为每一个 x 精确计算重叠部分的收益，然后取最大值。这部分的复杂度是 O(k)。

5. 最终策略 ​

结合以上分析，我们的高效解法就出来啦：

  1. 预处理：对每天的动物数量计算一个行内前缀和。这样我们就能在 O(1) 时间内算出任意区间 [L, R] 的动物总数了。
  2. 滚动数组DP：我们发现 dp[i] 只和 dp[i-1] 有关，所以可以用滚动数组来优化空间，只需要 dp_prev 和 dp_curr 两个数组。
  3. DP过程：
    • 对于每一天 i，从 2 到 n：
      • 首先根据 dp_prev 数组（即 dp[i-1] 的所有值），计算出它的前缀最大值数组 left_max_prev 和后缀最大值数组 right_max_prev。
      • 然后遍历当前相机位置 j 从 1 到 m-k+1：
        • 计算 dp_curr[j] 的值：
          • 基础值 = 第 i 天和第 i+1 天在 [j, j+k-1] 的动物数。
          • 候选项1：基础值 + left_max_prev[j-k] (处理左边不重叠的情况)
          • 候选项2：基础值 + right_max_prev[j+k] (处理右边不重叠的情况)
          • 候选项3...：遍历 x 从 max(1, j-k+1) 到 min(m-k+1, j+k-1)，计算 基础值 + dp_prev[x] - 重叠部分，取最大值。
        • dp_curr[j] 就是以上所有候选项中的最大值。
    • 循环结束后，dp_curr 成为新的 dp_prev，继续下一天的计算。

这样，每一天的状态转移复杂度就从 O(m^2) 降到了 O(m*k)，总时间复杂度就是 O(n*m*k)，完全可以通过啦！

代码实现喵~ ​

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

using namespace std;

int main() {
    // 使用C++标准库的快速IO，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    // 读入每天每个区域的动物数量
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    // 预处理每行的前缀和，方便O(1)计算区间和
    vector<vector<long long>> pre(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pre[i][j] = pre[i][j - 1] + a[i][j];
        }
    }

    const long long INF = -1e15; // 用一个很大的负数表示无效状态
    
    // DP滚动数组：dp_prev是上一天的结果，dp_curr是当前正在计算的结果
    vector<long long> dp_prev(m + 10, INF);
    vector<long long> left_max_prev(m + 10, INF); // 上一天的前缀最大值
    vector<long long> right_max_prev(m + 10, INF); // 上一天的后缀最大值

    vector<long long> dp_curr(m + 10, INF);
    
    // 初始化第一天的情况 (base case)
    // 第1天放相机，会拍第1天和第2天
    for (int j = 1; j <= m - k + 1; j++) {
        long long base;
        if (n > 1) {
            base = (pre[1][j + k - 1] - pre[1][j - 1]) + (pre[2][j + k - 1] - pre[2][j - 1]);
        } else { // 如果只有一天，就只拍第一天
            base = pre[1][j + k - 1] - pre[1][j - 1];
        }
        dp_curr[j] = base;
    }

    // 如果天数大于1，为下一次迭代准备好 prev 数组和前缀/后缀最大值数组
    if (n > 1) {
        vector<long long> left_temp(m + 10, INF);
        vector<long long> right_temp(m + 10, INF);
        for (int j = 1; j <= m - k + 1; j++) {
            left_temp[j] = (j == 1) ? dp_curr[j] : max(left_temp[j - 1], dp_curr[j]);
        }
        for (int j = m - k + 1; j >= 1; j--) {
            right_temp[j] = (j == m - k + 1) ? dp_curr[j] : max(right_temp[j + 1], dp_curr[j]);
        }
        left_max_prev = left_temp;
        right_max_prev = right_temp;
        dp_prev = dp_curr;
    }

    // DP主循环，从第二天开始
    for (int i = 2; i <= n; i++) {
        vector<long long> dp_curr2(m + 10, INF); // 当前天(i)的DP结果
        for (int j = 1; j <= m - k + 1; j++) {
            // 当前相机放在j，能拍到的基础动物数 (第i天和第i+1天)
            long long base;
            if (i < n) {
                base = (pre[i][j + k - 1] - pre[i][j - 1]) + (pre[i + 1][j + k - 1] - pre[i + 1][j - 1]);
            } else { // 最后一天特殊处理
                base = pre[i][j + k - 1] - pre[i][j - 1];
            }

            long long candidate = INF; // 存储dp[i][j]的候选最大值

            // 优化Case 1: 上一天的相机位置x在j的左边很远，无重叠
            if (j > k) {
                if (left_max_prev[j - k] != INF) {
                    candidate = max(candidate, base + left_max_prev[j - k]);
                }
            }

            // 优化Case 2: 上一天的相机位置x在j的右边很远，无重叠
            if (j + k <= m - k + 1) {
                if (right_max_prev[j + k] != INF) {
                    candidate = max(candidate, base + right_max_prev[j + k]);
                }
            }

            // 优化Case 3: 上一天的相机位置x和j有重叠，暴力枚举
            int x_low = max(1, j - k + 1);
            int x_high = min(m - k + 1, j + k - 1);
            for (int x = x_low; x <= x_high; x++) {
                if (dp_prev[x] == INF) continue;

                // 计算重叠区域 [L, R]
                int L = max(j, x);
                int R = min(j + k - 1, x + k - 1);
                long long overlap_val = 0;
                if (L <= R) {
                    // 重叠只发生在第i天
                    overlap_val = pre[i][R] - pre[i][L - 1];
                }
                long long value = base + dp_prev[x] - overlap_val;
                candidate = max(candidate, value);
            }
            dp_curr2[j] = candidate;
        }
        
        // 滚动数组，为下一次迭代做准备
        if (i < n) {
            vector<long long> left_temp(m + 10, INF);
            vector<long long> right_temp(m + 10, INF);
            for (int j = 1; j <= m - k + 1; j++) {
                left_temp[j] = (j == 1) ? dp_curr2[j] : max(left_temp[j - 1], dp_curr2[j]);
            }
            for (int j = m - k + 1; j >= 1; j--) {
                right_temp[j] = (j == m - k + 1) ? dp_curr2[j] : max(right_temp[j + 1], dp_curr2[j]);
            }
            left_max_prev = left_temp;
            right_max_prev = right_temp;
            dp_prev = dp_curr2;
        } else { // 如果已经是最后一天，结果就保存在dp_curr2里
            dp_curr = dp_curr2;
        }
    }

    // 在最后一天的所有可能放置位置中，找到最大的那个就是答案
    long long ans = 0; // 如果n=0或m<k，答案是0
    for (int j = 1; j <= m - k + 1; j++) {
        ans = max(ans, dp_curr[j]);
    }
    cout << ans << endl;

    return 0;
}

复杂度分析喵~ ​

  • 时间复杂度: O(n * m * k) 的说。

    • 我们有一个外层循环 i 从 1 到 n。
    • 里面有一个循环 j 从 1 到 m-k+1。
    • 在 j 循环内部，我们通过预处理的前/后缀最大值数组O(1)处理了不重叠的情况。对于重叠情况，我们有一个小循环 x，它最多迭代 2k-1 次。
    • 预处理前缀和是 O(n*m)，预处理每一天的前/后缀最大值是 O(m)。
    • 所以总的时间复杂度是 O(n * (m + m*k))，也就是 O(n*m*k)。对于这道题的 n 和 k 的限制，这个复杂度是完全可以接受的，喵~

  • 空间复杂度: O(n * m) 的说。

    • 主要的空间开销是存储输入数据 a 和前缀和数组 pre，它们都是 n x m 的。
    • DP数组我们用了滚动数组的技巧，所以只需要 O(m) 的空间。
    • 因此总空间复杂度由输入和前缀和主导，为 O(n*m)。

知识点与总结喵~ ​

这道题是一道非常经典的 DP优化 题目，值得好好回味一下呐！

  1. 核心思想: 动态规划。通过定义 dp[i][j] 来解决按时间推进的最优化问题。
  2. 关键优化: 识别并优化DP转移的瓶颈。从 O(m^2) 的转移优化到 O(m*k)，关键在于对前一状态 x 的位置进行分类讨论：
    • 远距离/不重叠: 使用前缀/后缀最大值进行 O(1) 查询。
    • 近距离/重叠: 利用 k 较小的特点，进行局部暴力枚举。 这种“分情况讨论+预处理”的优化思路在很多DP题中都很有用哦！
  3. 基础技巧:
    • 前缀和: 快速计算区间和，是各种区间问题的必备神器。
    • 滚动数组: 当DP状态只依赖于前一两个状态时，用它来优化空间，防止内存爆炸。

希望这篇题解能帮到你，喵~！只要多加练习，你也能成为DP大师的！加油哦！(ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe