D. Remove One Element - 题解

比赛与标签

比赛: Codeforces Round 605 (Div. 3) 标签: brute force, dp 难度: *1500

题目大意喵~

哈喵~！各位阿尔法城的大佬们，今天我们来攻略一道很有趣的题目哦！

题目给了我们一个由 n 个整数组成的数组 a，我们最多可以从里面拿走一个元素（当然，也可以一个都不拿）。

我们的任务是，在操作后的数组里，找到一个最长的、连续的、并且数值是严格递增的子数组，然后告诉本喵它的长度是多少，的说！

比如说，对于数组 [1, 2, 5, 3, 4]，如果我们把 5 这个元素拿走，数组就变成了 [1, 2, 3, 4]。这个新数组本身就是一个长度为 4 的严格递增子数组，超棒的对吧！这就是我们要找的答案啦，喵~

解题思路喵~

这道题呀，看起来有点小复杂，但只要我们把情况分清楚，就一点都不可怕啦！我们可以把问题分成两种主要情况来考虑，呐~

情况一：一个元素都不删除！

最简单的情况就是我们什么都不做，保留原数组。这时候，我们只需要找到原数组里最长的那个连续递增子数组的长度就可以了。这个很简单嘛，从头到尾扫一遍就能搞定。不过，为了配合第二种情况，我们可以用一个更通用的方法——动态规划（DP）来解决！

情况二：删除一个元素！

这才是这道题的精髓所在，喵！( •̀ ω •́ )✧

想象一下，我们把第 i 个元素 a[i] 给删掉了。会发生什么呢？原本在 a[i] 这里可能会断开的两个递增序列，现在有机会“手拉手”连接起来了！

具体来说，就是 a[i] 左边的那个以 a[i-1] 结尾的递增序列，和 a[i] 右边的那个从 a[i+1] 开头的递增序列。

它们能连起来的条件是什么呢？当然是 a[i-1] 必须小于 a[i+1] 啦！这样才能维持我们“严格递增”的队形嘛。如果这个条件满足，那么连接后的新序列长度就是：(以 a[i-1] 结尾的递增序列长度) + (从 a[i+1] 开头的递增序列长度)。

DP 闪亮登场！

为了能快速得到上面我们需要的两种长度，动态规划就是我们最好的朋友！

1. 从左向右DP: 我们定义一个数组 len_l[i]，表示在原数组中，以 a[i] 结尾的最长连续递增子数组的长度。

   • 我们可以从左到右遍历来计算它。
   • 如果 a[i] > a[i-1]，说明 a[i] 可以接在 a[i-1] 后面，让递增序列变得更长，所以 len_l[i] = len_l[i-1] + 1。
   • 否则，a[i] 无法接续，只能自己重新开始一个长度为 1 的递增序列，即 len_l[i] = 1。

2. 从右向左DP: 同理，我们再定义一个数组 len_r[i]，表示在原数组中，以 a[i] 开头的最长连续递增子数组的长度。

   • 这次我们从右到左遍历来计算。
   • 如果 a[i] < a[i+1]，说明 a[i] 可以作为 a[i+1] 前面的一个元素，所以 len_r[i] = len_r[i+1] + 1。
   • 否则，a[i] 只能自己当头，len_r[i] = 1。

整合答案！

预处理完 len_l 和 len_r 两个数组之后，答案就呼之欲出啦！

1. 首先，不删除元素时的最大长度就是 len_l 数组里的最大值（或者 len_r 的也一样）。我们先把它作为我们的初始答案 max_len。

   • 一个小细节: 如果我们删除的是第一个或最后一个元素，比如删掉 a[0]，那么最长的递增子数组就完全在 a[1...n-1] 内部。这种情况的最优解，其实已经被我们这一步计算 max(len_l) 的过程覆盖了，所以不需要额外操心，喵~

2. 然后，我们遍历所有可以被删除的中间元素 a[i]（也就是 i 从 1 到 n-2）。

   • 检查是否满足连接条件 a[i-1] < a[i+1]。
   • 如果满足，我们就计算出连接后的长度 len_l[i-1] + len_r[i+1]，然后用它来更新我们的 max_len。

最后，遍历完所有可能的删除点后，max_len 中存储的就是最终的答案啦！是不是很清晰呢？(ฅ'ω'ฅ)

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>

// 主函数，解决问题的地方喵~
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 对于 n >= 2 的情况，通用逻辑都适用，所以不需要特殊处理 n=2 的情况~
    
    // len_l[i]: 喵~ 这是从左到右的DP，计算以 a[i] 结尾的最长递增子数组长度
    std::vector<int> len_l(n, 1);
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            len_l[i] = len_l[i - 1] + 1;
        }
    }

    // len_r[i]: 喵~ 这是从右到左的DP，计算以 a[i] 开头的最长递增子数组长度
    std::vector<int> len_r(n, 1);
    for (int i = n - 2; i >= 0; --i) {
        if (a[i] < a[i + 1]) {
            len_r[i] = len_r[i + 1] + 1;
        }
    }

    // 情况1: 一个元素都不删。
    // 最长长度就是所有 len_l[i] 里的最大值，这是我们的基准答案。
    int max_len = 0;
    if (n > 0) {
        max_len = 1; // 至少有一个元素，所以长度至少为1
    }
    for (int len : len_l) {
        max_len = std::max(max_len, len);
    }

    // 情况2: 删除一个元素 a[i] (1 <= i < n-1)。
    // 这可能会把以 a[i-1] 结尾的递增序列和以 a[i+1] 开头的递增序列连接起来。
    // 连接条件是 a[i-1] < a[i+1]。
    // 连接后的长度是 len_l[i-1] + len_r[i+1]。
    // 我们遍历所有可能的删除点 i (从 1 到 n-2) 来检查这种情况。
    for (int i = 1; i < n - 1; ++i) {
        if (a[i - 1] < a[i + 1]) {
            // 就像这样把两段拼起来！ (ฅ'ω'ฅ)
            max_len = std::max(max_len, len_l[i - 1] + len_r[i + 1]);
        }
    }
    
    // 关于删除第一个或最后一个元素的说明喵：
    // 如果我们删除 a[0]，最长的递增子数组就在 a[1...n-1] 里。
    // 任何在 a[1...n-1] 里的递增子数组，也都是原数组 a 的递增子数组。
    // 所以它的长度已经在我们第一步计算 max(len_l) 时被考虑过了。
    // 删除 a[n-1] 同理。所以我们只需要显式地检查中间元素的合并情况就够啦。

    std::cout << max_len << std::endl;
}

int main() {
    // 快速 I/O，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析喵~

• 时间复杂度: O(n) 的说。我们对数组进行了三次独立的线性扫描：一次从左到右计算 len_l，一次从右到左计算 len_r，还有一次遍历所有可能的断点来检查合并。每次扫描都是 O(n) 的，所以总时间复杂度是 O(n) + O(n) + O(n) = O(n)，非常高效！
• 空间复杂度: O(n) 的说。我们使用了两个额外的数组 len_l 和 len_r 来存储 DP 状态，每个数组的大小都是 n，所以空间复杂度是 O(n)。

知识点与总结喵~

这道题真是一道将 动态规划 和 分类讨论 结合得很好的题目呢！

1. DP预处理: 通过 len_l 和 len_r 两个DP数组，我们巧妙地预处理了“以某个点结尾/开头的最长递增序列长度”这个子问题。这种“左右开弓”分别计算前缀和后缀信息的DP技巧，在处理类似的区间、断点、分割点问题时非常有用哦！

2. 分类讨论与逻辑简化: 将问题分解为“不删除”和“删除一个”两种情况，让复杂的逻辑变得清晰。特别是对于“删除一个”的情况，我们进一步分析出只有在删除点 i 处满足 a[i-1] < a[i+1] 时，才有可能产生更优的解。这种逻辑上的化简是解题的关键呐！

3. 边界处理: 聪明地处理边界情况能让代码更简洁。我们发现删除首尾元素的情况，其实已经被“不删除”时的最大值计算所包含了，因此无需特殊处理，只需要关注中间元素的删除即可。

希望这次的讲解对你有帮助哦！继续加油，你就是最棒的，喵~ (ฅ´ω`ฅ)