喵~ 主人好呀！今天由我，你最可爱的小猫娘，来为你讲解一道有趣的动态规划问题——Block Sequence (CF 1881E) 喵！

这个问题就像是整理一排猫抓板，要让它们排列得整整齐齐、漂漂亮亮的，一起来看看怎么做吧！

题目大意

题目会给我们一个长度为 n 的整数序列 a。

我们需要把这个序列变成一个“美丽序列”。什么样的序列是“美丽序列”呢？一个序列如果能被分成若干个“块”，并且每个块都满足 “块的第一个元素”等于“这个块的长度”，那么它就是美丽的喵。

举个例子：序列 [3, 3, 4, 5, 2, 6, 1] 就是一个美丽序列。 它可以被分成两个块：

1. 第一个块是 [3, 3, 4, 5]。它的第一个元素是 3，但整个块的长度是 4，这不对喵... 啊，我搞错了，让本喵再看看！ 正确的划分应该是：[3, 3, 4, 5] 和 [2, 6, 1]。
   • 第一个块是 [3, 3, 4, 5]。它的第一个元素是 3，而这个块恰好由 3 个元素（3, 4, 5）跟在它后面，所以总长度是 1 + 3 = 4。啊，题目里的意思是块的第一个元素是块的长度！所以 [3, 3, 4, 5] 的第一个元素是 3，那么这个块就应该是 [3, x, y] 这样子，长度为 3。
   • 让我们重新理解一下喵~！一个块的形式是 [k, element_1, element_2, ..., element_k]。所以，整个块的长度是 k+1。
   • 那么，[3, 3, 4, 5, 2, 6, 1] 这个序列，应该是这样划分的：
     • 第一个块：[3, 3, 4, 5]。它的第一个元素是 3，后面跟着 3 个元素 3, 4, 5。这个块是合法的。
     • 第二个块：[2, 6, 1]。它的第一个元素是 2，后面跟着 2 个元素 6, 1。这个块也是合法的。
   • 所以，[3, 3, 4, 5, 2, 6, 1] 是一个美丽序列！

而序列 [1, 4, 3] 就不是，因为第一个块的长度应该是 1，那么块本身就是 [1]。多出来的 4, 3 就没法处理了。

我们每次操作可以从序列中 删除任意一个元素。

问题是：最少需要多少次删除操作，才能让原始序列变成一个美丽序列呢？

题解方法

这个问题要求“最少操作次数”，一看到这种最优化问题，本喵的直觉就告诉我，可以用 动态规划 (Dynamic Programming, DP) 来解决！就像猫猫总能找到最舒服的午睡地点一样喵~

我们的思路是从后往前看这个序列。为什么从后往前呢？因为一个块 [k, ...] 的决策会影响到它后面的序列，从后往前处理，可以保证当我们在决定位置 i 的元素何去何从时，它后面所有可能的情况我们都已经算过了，拿到了最优解。

我们来定义一个 dp 数组，就像猫猫的小鱼干仓库一样喵~ dp[i] 表示：将原始序列的后缀 a[i...n-1] 变成本地序列，最少需要删除多少个元素。

我们的最终目标，就是求出 dp[0]，也就是让整个序列 a[0...n-1] 变美丽的最小删除次数。

接下来，我们来思考 dp[i] 该怎么计算。对于在位置 i 的元素 a[i]，我们有两种选择，就像猫猫看到一个毛线球，是扑上去玩呢，还是不理它走开呢？

1. 删除 a[i] (不理它走开喵~) 如果我们决定删除 a[i]，那么我们就付出了 1 次删除操作的代价。接下来，问题就变成了“如何让剩下的后缀 a[i+1...n-1] 变美丽”，而这个问题的答案，我们已经定义好了，就是 dp[i+1]！ 所以，这种选择的总代价是 1 + dp[i+1]。

2. 保留 a[i] (扑上去玩！) 如果我们决定保留 a[i]，那么它必须成为一个新块的开始。设 a[i] 的值是 k。根据美丽序列的定义，这个新块的长度应该是 k，它会包含 a[i] 自己，以及它后面的 k 个元素。 也就是说，这个块会占用序列中从 i 到 i+k 的所有位置。 这个选择有一个前提条件：数组得有足够多的元素来组成这个块，也就是 i + k 不能超过数组的末尾。换句话说，下一个块的起始位置 i + k + 1 必须小于等于 n（n 是数组的长度，n 这个下标可以看作是数组末尾之后的位置）。 如果这个条件满足，我们就可以成功地组成一个块 [a[i], a[i+1], ..., a[i+k]]。我们没有删除这个块里的任何元素。接下来，问题就变成了“如何让从 i + k + 1 开始的后缀 a[i+k+1...n-1] 变美丽”，这个问题的答案就是 dp[i+k+1]。 所以，这种选择的总代价是 dp[i+k+1]。

综合以上两种选择，dp[i] 就应该是这两种选择中，代价更小的那一个！ 所以我们的状态转移方程就是： dp[i] = 1 + dp[i+1] (这是默认选择，即删除 a[i]) 如果 i + a[i] + 1 <= n，那么我们还有一个选择：dp[i] = min(dp[i], dp[i + a[i] + 1])

最后，我们需要一个 边界条件。当 i=n 时，dp[n] 表示要让一个空序列（从下标 n 开始的后缀）变美丽需要多少次删除。空序列本身就是美丽的，所以 dp[n] = 0。

我们从 i = n-1 开始，一步步倒着计算到 i = 0，最终 dp[0] 就是我们想要的答案啦！

题解

下面是具体的 C++ 代码实现，本喵加了一些注释，方便主人理解喵~

#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];
    }

    // dp[i] 表示将后缀 a[i...n-1] 变美丽所需的最小删除次数。
    // 数组大小为 n+1，是为了处理边界情况 dp[n]。
    std::vector<int> dp(n + 1);

    // 边界条件：一个空后缀是美丽的，不需要删除任何元素。
    dp[n] = 0;

    // 我们从后往前遍历数组来计算 dp 值。
    // 这样可以确保在计算 dp[i] 时，所有它依赖的 dp 值（如 dp[i+1]）都已经计算好了。
    for (int i = n - 1; i >= 0; --i) {
        // 选择 1：删除 a[i]。
        // 代价是 1 (删除 a[i]) + dp[i+1] (处理剩余部分的代价)。
        dp[i] = 1 + dp[i + 1];

        // 选择 2：保留 a[i]，并以它为首构建一个块。
        // 块的长度由 a[i] 决定。
        int k = a[i];
        
        // 下一个块的起始下标。
        int next_start_idx = i + k + 1;

        // 检查是否能构成一个完整的块（即块不会超出数组边界）。
        if (next_start_idx <= n) {
            // 如果可以，那么这个选择的代价就是处理从 next_start_idx 开始的后缀的代价。
            // 我们在两种选择中取一个最小值。
            dp[i] = std::min(dp[i], dp[next_start_idx]);
        }
    }

    // dp[0] 存储了处理整个数组 a[0...n-1] 的最小删除次数。
    std::cout << dp[0] << "\n";
}

int main() {
    // 加上这个可以让输入输出快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题的核心知识点是 动态规划 (Dynamic Programming, DP)。

什么是动态规划？ 动态规划是一种通过将复杂问题分解成更小的、重叠的子问题来解决问题的算法思想。它通常用于求解最优化问题（如求最大值、最小值、最长序列等）。

动态规划的两个核心特性：

1. 最优子结构 (Optimal Substructure) 如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么这个问题就具有最优子结构。 在这道题里，让整个序列 a[0...n-1] 变美丽的最小删除次数，依赖于让其后缀 a[1...n-1] 或 a[k+1...n-1] 变美丽的最小删除次数。这就是最优子结构的体现。

2. 重叠子问题 (Overlapping Subproblems) 在用递归等方式解决问题时，如果相同的子问题被反复计算多次，那么这个问题就具有重叠子问题的性质。 比如，在计算 dp[i] 和 dp[j] 时，它们可能都需要 dp[k] 的值。动态规划通过“记忆化”或“自底向上”的填表方式，确保每个子问题只被计算一次，然后将结果存储起来，供后续计算使用，从而大大提高了效率。

我们这道题的解法就是典型的“自底向上”填表法。我们从最小的子问题 dp[n] 开始，然后逐步计算更大的子问题 dp[n-1], dp[n-2], ..., 直到我们要求解的原始问题 dp[0]。这样就保证了计算的顺序是正确的，并且每个子问题只求解一次。

希望这篇题解能帮到主人哦，如果还有什么不明白的，随时可以再来问本喵！喵~