NekoNowcoder

Appearance

可划分数组 - 题解 ​

标签与难度 ​

标签: 动态规划, 数论, 最大公约数, 预处理, 数组划分, 复杂度优化 难度: 1900

题目大意喵~ ​

主人你好呀~！这道题是这样的喵：

给你一个长度为 nn 的整数数组 a1,a2,…,ana_1, a_2, \dots, a_n。你的任务是把这个数组切成尽可能多的连续小段。不过呢，这个切法有几个规矩要遵守哦：

  1. 分段要彻底：第一段必须从数组头 a1a_1 开始，最后一段必须在数组尾 ana_n 结束，中间的段要紧紧挨在一起，不能有空隙也不能重叠。
  2. 段长有要求：每一段的长度都不能太短，至少要为 2。
  3. 最重要的规矩：在任何一段里面，随便挑一个数，它都必须能在这一段里找到一个“好朋友”（也就是另一个数），使得它俩不互质（最大公约数大于 1）。换句话说，段内的任何一个数都不能“孤单”，不能和段内所有其他数都互质哦！

你的目标是找到一种划分方法，让段的数量 kk 最大。如果找不到任何满足条件的划分，就告诉人家 -1 好了，喵~

举个栗子：数组 [6, 10, 7, 7] 一种划分可以是 [6, 10] 和 [7, 7]。

  • 在 [6, 10] 里, gcd(6, 10) = 2 > 1。6 和 10 互为好朋友，满足条件。
  • 在 [7, 7] 里, gcd(7, 7) = 7 > 1。两个 7 互为好朋友，也满足条件。 这种划分有 2 段，是合法的。

解题思路分析 ​

这道题要求我们最大化划分的段数，一看到“最大化”、“划分”这类字眼，我的DNA就动了，这不就是动态规划（DP）的经典场景嘛，喵！

1. 定义DP状态 ​

一个很自然的思路是，我们从左到右处理数组。我们可以定义 dp[i] 表示：将数组的前 i 个元素 a[1...i] 划分为若干合法段，能得到的最大段数是多少。

我们的最终目标就是 dp[n] 的值。

2. 思考DP转移 ​

要计算 dp[i]，我们可以考虑最后一段是怎么形成的。假设最后一段是从索引 j 开始，到索引 i 结束，也就是子数组 a[j...i]。 如果 a[j...i] 本身是一个合法的段，那么我们就可以从一个已经划分好的 a[1...j-1] 状态转移过来。 所以，状态转移方程的雏形就是：

dp[i]=max⁡1≤j≤i{dp[j−1]+1}(前提是子数组 a[j...i] 是一个合法的段)dp[i] = \max_{1 \le j \le i} \{ dp[j-1] + 1 \} \quad (\text{前提是子数组 } a[j...i] \text{ 是一个合法的段})

我们约定 dp[0] = 0，表示空前缀有 0 个段。

3. 核心挑战：如何判断段的合法性？ ​

现在问题就变成了，如何快速判断一个子数组 a[j...i] 是否合法呢？ 根据题目要求，一个段 a[j...i] 合法，需要满足两个条件：

  1. 长度至少为 2，即 i - j + 1 >= 2。
  2. 对于段中的每一个元素 a_k (j≤k≤ij \le k \le i)，都存在另一个元素 a_p (j≤p≤i,p≠kj \le p \le i, p \ne k)，使得 gcd(a_k, a_p) > 1。

这个“每个元素都要有伴”的条件有点绕。我们不妨反过来想：一个段什么时候是 不合法 的？ 当段 a[j...i] 中存在一个“孤单”的元素 a_k，它和段内所有其他元素都互质。

如果我们直接在DP转移中检查这个条件，对于每个 i，我们遍历 j，对于每个 j，我们再遍历 k from j to i 去检查 a_k 是否孤单，这会导致一个 O(N3)O(N^3) 的算法，对于 N=2000N=2000 来说，肯定会超时的说！我的爪子可受不了这么慢的计算！

4. 优化合法性检查：预处理大法！ ​

为了加速判断，我们可以预处理一些信息。对于每个元素 a_k，它在整个数组中的“好朋友”在哪里呢？我们可以预先计算出：

  • prev_link[k]: 在 k 左边，离 k 最近的，且与 a_k 不互质的元素的索引。
  • next_link[k]: 在 k 右边，离 k 最近的，且与 a_k 不互质的元素的索引。

这个预处理可以通过两层循环完成，复杂度是 O(N2⋅log⁡A)O(N^2 \cdot \log A)，其中 AA 是数组中的最大值，log A 是计算 gcd 的开销。对于本题数据范围是完全可以接受的。

有了 prev_link 和 next_link，我们再来看“孤单”的定义： 在段 a[j...i] 中，元素 a_k 是孤单的，当且仅当它所有的“好朋友”都在这个段的 外面。也就是说： prev_link[k] < j 并且 next_link[k] > i。

现在，段 a[j...i] 是合法的，当且仅当 不存在 任何一个 k (j≤k≤ij \le k \le i) 满足 prev_link[k] < j 且 next_link[k] > i。

5. 最终的 O(N2)O(N^2) DP方案 ​

虽然我们有了快速判断“孤单”的方法，但如果在DP中对每个 [j, i] 都遍历一遍 k，仍然是 O(N3)O(N^3)。我们需要更快的办法！

让我们重新审视DP循环。当我们计算 dp[i] 时，我们从 j = i 开始，一步步往前枚举段的起点 j。 对于一个固定的终点 i，当起点 j 从 i 向 1 移动时，我们考察的段 [j, i] 在不断变长。

我们可以维护一个变量，比如说 min_required_start。它表示，为了让从 j 到 i 这些元素都不“孤单”，段的起点 j 最晚 要从哪里开始。

具体来说，当我们从 j=i 扫到 j=1 时：

  • 我们考察当前元素 a_j。
  • 如果 a_j 在 i 的右边没有好朋友 (即 next_link[j] > i)，那么它必须在段内找到一个左边的好朋友。这意味着段的起点必须在 prev_link[j] 或其左边。所以，为了满足 a_j，段的起点至少要延伸到 prev_link[j]。
  • 我们用 min_required_start 来记录所有从 j 到 i 中，像 a_j 这样“右边没朋友”的元素，它们所要求的 prev_link 的最小值。
  • 在每一步 j，我们更新 min_required_start： if (next_link[j] > i) min_required_start = min(min_required_start, prev_link[j])
  • 然后我们检查，当前的起点 j 是否满足了所有从 j 到 i 元素的要求？也就是 j <= min_required_start？
  • 如果 j <= min_required_start，并且段长 i - j + 1 >= 2，并且 dp[j-1] 是一个有效的状态，那么我们就找到了一个合法的转移：dp[i] = max(dp[i], dp[j-1] + 1)。

通过这种方式，我们在一个 O(N)O(N) 的内层循环中，同时完成了段的合法性检查和DP转移，总的时间复杂度就降到了 O(N2)O(N^2)，可以顺利通过啦！喵~

哦对了，还有一个小细节：如果数组里有数字 1，那它和任何数（除了它自己）的 gcd 都是 1，所以它永远是“孤单”的。遇到这种情况，直接输出 -1 就好啦。

代码实现 ​

这是我根据上面的思路，精心重构的代码哦，注释超详细的，希望能帮到你，喵~

cpp
#include <iostream>
#include <vector>
#include <numeric> // For std::gcd
#include <algorithm> // For std::min and std::max

// 一个简单的求最大公约数的函数
int gcd(int a, int b) {
    return std::gcd(a, b);
}

int main() {
    // 使用C++标准IO加速，让程序跑得像猫一样快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 使用1-based索引，和题目描述保持一致，喵~
    std::vector<int> a(n + 1);
    bool has_one = false;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        if (a[i] == 1) {
            has_one = true;
        }
    }

    // 特殊情况：如果数组里有1，它永远找不到不互质的伙伴，直接无解
    if (has_one) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // --- 预处理阶段 ---
    // prev_link[i]：a[i]左边最近的不互质数的位置
    // next_link[i]：a[i]右边最近的不互质数的位置
    std::vector<int> prev_link(n + 2, 0);
    std::vector<int> next_link(n + 2, n + 1);

    for (int i = 1; i <= n; ++i) {
        // 找左边的伙伴
        for (int j = i - 1; j >= 1; --j) {
            if (gcd(a[i], a[j]) > 1) {
                prev_link[i] = j;
                break; // 找到最近的就跑
            }
        }
        // 找右边的伙伴
        for (int j = i + 1; j <= n; ++j) {
            if (gcd(a[i], a[j]) > 1) {
                next_link[i] = j;
                break; // 找到最近的就跑
            }
        }
    }

    // --- 动态规划阶段 ---
    // dp[i]：将前i个元素划分能得到的最大段数
    // 初始化为-1表示不可达，dp[0]=0是我们的起点
    std::vector<int> dp(n + 1, -1);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        // min_required_start: 为了满足[j...i]中所有右边没朋友的元素，
        // 段的起点j最晚要到哪里。
        int min_required_start = i; // 初始为一个不可能的值

        // 从后往前枚举最后一段的起点j
        for (int j = i; j >= 1; --j) {
            // 考虑元素a[j]，如果它在当前段[j...i]的右边没有伙伴...
            if (next_link[j] > i) {
                // ...那么它必须依赖左边的伙伴，所以段的起点必须不晚于prev_link[j]
                min_required_start = std::min(min_required_start, prev_link[j]);
            }

            // 检查段[j...i]是否合法
            // 1. 所有在[j...i]中右边没朋友的元素，它们要求的左伙伴起点(min_required_start)
            //    必须被当前起点j满足，即 j <= min_required_start
            //    注意：这里的逻辑是 min_required_start 必须大于等于 j (即 prev_link[k] >= j)
            //    所以是 min_required_start >= j
            // 2. 段长 i-j+1 >= 2
            // 3. 前面的划分 dp[j-1] 必须是可达的
            if (min_required_start >= j && (i - j + 1 >= 2) && dp[j - 1] != -1) {
                dp[i] = std::max(dp[i], dp[j - 1] + 1);
            }
        }
    }

    std::cout << dp[n] << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N2⋅log⁡A)O(N^2 \cdot \log A)

    • 预处理 prev_link 和 next_link 的部分，有两层嵌套循环，内部有一次 gcd 计算。gcd 的复杂度大约是 O(log⁡A)O(\log A)，其中 AA 是数组中元素的最大值。所以这部分是 O(N2⋅log⁡A)O(N^2 \cdot \log A)。
    • 动态规划部分，有两层嵌套循环 i 和 j，内部操作是常数时间。所以这部分是 O(N2)O(N^2)。
    • 综上，总的时间复杂度由预处理主导，为 O(N2⋅log⁡A)O(N^2 \cdot \log A)。对于本题数据范围，这完全足够快了，喵~

  • 空间复杂度: O(N)O(N)

    • 我们主要使用了 a, prev_link, next_link, dp 这几个数组，它们的大小都和输入规模 NN 成正比。因此，空间复杂度是 O(N)O(N)。

知识点总结 ​

这道题真是一次有趣的冒险，我们来总结一下探险中学到的东西吧！

  1. 动态规划思想: 遇到求解最优划分、最大/最小计数的问题，首先可以考虑DP。定义好状态和转移方程是解题的第一步。
  2. 逆向思维: "所有元素都满足A" 这个条件不好判断时，可以试试从反面思考 "是否存在一个元素不满足A"。这常常能让问题变得更清晰。
  3. 预处理: 当DP转移中需要反复查询某些固定属性时，可以先把这些属性计算出来存好。这是典型的“空间换时间”策略，非常有效！
  4. O(N3)O(N^3) 到 O(N2)O(N^2) 的优化: 本题的核心就是将朴素的DP优化。通过在内层循环中维护一个状态（min_required_start），我们避免了重复的检查，将复杂度降低了一个数量级。这种边遍历边维护信息的技巧在很多DP优化中都会用到哦。
  5. 细节处理: 不要忘记处理像 a[i] = 1 这样的边界情况和特殊值，它们有时是解题的关键，有时是陷阱，要小心哦，喵~

希望这篇题解能帮到你！继续加油，享受算法的乐趣吧，喵呜~！