题解 | #相助(easy)#

问题分析

1. 操作性质分析 题目定义的操作是：选择 $a_i = a_j$ 的一对索引并删除区间 $[i, j]$ 。这一操作看似是“消除”操作，但我们可以从逆向或者等价转换的角度来理解：

若要使数组清空，数组中的每一个元素都必须属于某一次消除操作。
虽然操作会导致剩余元素拼接（索引变化），但从原始数组的视角看，任何一次操作实际上都是移除了原始数组中的一个连续子段（或拼接后形成的相邻段）。
关键结论：该问题等价于将原数组 $A$ 在逻辑上划分（Partition） 为 $k$ 个不相交的连续子段 $S_1, S_2, ..., S_k$ 。每个子段 $S_m = A[l \dots r]$ 必须满足以下两个条件才能被合法消除：
1. 首尾相等： $A[l] == A[r]$ 。
2. 长度合法：由于 $i < j$ ，子段长度必须至少为 2（即 $r - l + 1 \ge 2$ ）。

为什么是划分而不是嵌套？ 有疑问可能会认为：是否存在一种情况，先删除内部一段（如 1 0 0 1 中先删 0 0），以此让外部相邻从而消除外部（剩余 1 1 再消除）？

对于 1 0 0 1：
- 策略 A（嵌套消除）：先删 00 (1次)，剩 11，再删 11 (1次)。总共 2 次。
- 策略 B（直接消除）：直接删 1 0 0 1 (首尾皆为 1)。总共 1 次。
贪心性质：对于最小化操作次数的目标，只要外部能构成合法消除条件（首尾相等），直接消除外部大约束总是优于或等价于先消除内部。因此，我们只需要考虑将数组切分为若干个不相交的合法区间即可，无需模拟复杂的消除过程。

算法：线性动态规划 (Linear DP)

基于上述“最短不相交划分”的转化，这是一个典型的线性 DP 问题。

1. 状态定义

设 $dp[i]$ 表示将原数组的前缀 $a[1 \dots i]$ 完全清空所需的最少操作次数。

如果前缀 $a[1 \dots i]$ 无法完全消除，则 $dp[i] = \infty$ 。
初始状态： $dp[0] = 0$ （空数组需要 0 次操作）。

2. 状态转移方程

对于当前位置 $i$ ，我们希望找到一个切分点 $j$ ( $0 \le j < i$ )，使得 $a[j+1 \dots i]$ 这一段可以作为一个整体被一次性消除。

消除条件：
1. 这段区间的首尾元素相等： $a[j+1] == a[i]$ 。
2. 区间长度至少为 2： $i - (j+1) + 1 \ge 2 \implies i - j \ge 2 \implies j \le i-2$ 。
转移逻辑： $dp[i] = \min \{ dp[j] + 1 \}$ 其中 $j$ 需满足： $0 \le j \le i-2$ 且 $a[j+1] == a[i]$ 。

3. 复杂度瓶颈与优化

如果直接暴力枚举 $j$ ，总时间复杂度为 $O(N^2)$ 。鉴于 $N \le 5 \times 10^5$ ，这会超时。我们需要 $O(N)$ 的解法。

优化思路：我们需要快速找到满足条件的最小 $dp[j]$ 。观察条件 $a[j+1] == a[i]$ ，该条件只与 $a[j+1]$ 的值有关。我们可以维护两个变量（对应值 0 和 1），分别记录“下一位是 0”和“下一位是 1”的那些位置 $j$ 中， $dp[j]$ 的最小值。

令 min_cost[Val] 表示所有满足 $a[k+1] == Val$ 的有效下标 $k$ 中， $dp[k]$ 的最小值。

当我们在计算 $dp[i]$ 时，我们需要查找的是起跳点 $j$ 。这个起跳点的特征是：它后面紧跟的元素（即区间的开头 $a[j+1]$ ）必须等于当前的结尾 $a[i]$ 。
因此， $dp[i] = \text{min_cost}[a[i]] + 1$ 。

延迟更新机制（处理长度 $\ge 2$ 的约束）：由于区间长度必须 $\ge 2$ ，当我们计算 $dp[i]$ 时，只能利用 $j \le i-2$ 的状态。这意味着，第 $i-2$ 个位置的状态 $dp[i-2]$ 直到我们在处理第 $i$ 个位置时，才变得“可用”（因为此时新区间长度正好达到 2）。所以在处理 $i$ 的开始，我们将 $dp[i-2]$ 的信息更新进 min_cost 数组中。具体来说，是更新 min_cost[a[i-1]]，因为 $dp[i-2]$ 是作为 $a[i-1]$ 开头那段的前驱状态。

代码实现

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

static constexpr int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> dp(n + 1, INF);
    vector<int> minCost(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int prev = i - 2;
        if (prev >= 0) {
            int target = a[prev + 1];
            minCost[target] = min(minCost[target], dp[prev]);
        }

        int curVal = a[i];
        int bestPrev = minCost[curVal];
        if (bestPrev != INF)
            dp[i] = bestPrev + 1;
    }

    if (dp[n] == INF)
        cout << "-1\n";
    else
        cout << dp[n] << "\n";
}