题目大意

有一个由 $n$ 个积木搭成的塔，每个积木上有一个数字 $a_i$，表示这个积木应该处在的高度（从底部开始计数）。我们需要移除一些积木，使得留在塔中且处在正确高度的积木数量最大化。

正确高度的定义：如果一个积木在移除后的塔中处于第 $j$ 层（从底部数起），且这个积木上的数字 $a_i = j$，那么它处在正确高度。

关键观察

1. 问题本质：我们要找到一个子序列（保留的积木），使得这个子序列中满足 $a_i = \text{位置索引}$ 的积木数量最多
2. 位置变化：当我们移除一些积木后，剩余积木的位置会重新编号
3. 最优结构：在最优解中，保留的积木序列中，满足 $a_i = i'$ 的积木会形成一个递增序列（其中 $i'$ 是重新编号后的位置）

问题转化

设我们保留的积木在原序列中的下标为 $i_1 < i_2 < \cdots < i_k$（从底部开始），它们在新的塔中分别处于位置 $1, 2, \ldots, k$。

我们想要最大化满足 $a_{i_j} = j$ 的 $j$ 的数量。

动态规划思路

状态定义

令 $dp[i]$ 表示考虑前 $i$ 个积木，且第 $i$ 个积木保留并在新塔中处于某个位置时，能够获得的最大正确积木数量。

状态转移

对于第 $i$ 个积木：

• 如果保留它，那么它在新塔中的位置至少是 $1$，最多是 $i$
• 如果 $a_i \leq i$，那么我们可以让它在新的塔中处于第 $a_i$ 个位置
• 在这种情况下，我们需要在前 $i-1$ 个积木中找出一个积木 $j$，使得 $a_j = a_i - 1$ 且 $j < i$

更精确地说：

$$dp[i] = \max(1, \max_{j < i, a_j = a_i - 1} dp[j] + 1) $$

优化

直接这样转移是 $O(n^2)$ 的，对于 $n \leq 10^5$ 会超时。

优化方法：

• 用数组 $last[x]$ 记录目前为止数字 $x$ 对应的最大 $dp$ 值
• 这样我们可以在 $O(1)$ 时间内找到对于 $a_i$，$a_i-1$ 对应的最大 $dp$ 值

算法步骤

1. 初始化 $dp$ 数组为 $0$，$last$ 数组为 $0$
2. 遍历 $i$ 从 $1$ 到 $n$：
   • 如果 $a_i \leq i$：
     • $dp[i] = last[a_i - 1] + 1$（如果 $last[a_i - 1] > 0$）
     • 否则 $dp[i] = 1$（如果 $a_i = 1$ 或者可以作为序列开头）
   • 更新 $last[a_i] = \max(last[a_i], dp[i])$
3. 找到最大的 $dp[i]$，记录对应的位置
4. 反向追踪构造移除方案

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> dp(n + 1, 0);      // dp[i]：以i结尾的最大正确数
    vector<int> last(n + 2, 0);    // last[x]：数字x对应的最大dp值
    vector<int> prev(n + 1, 0);    // 记录前驱
    
    int max_dp = 0, max_pos = 0;
    
    for (int i = 1; i <= n; i++) {
        if (a[i] <= i) {  // 这个积木有可能在正确位置
            if (a[i] == 1) {
                dp[i] = 1;
                prev[i] = 0;
            } else if (last[a[i] - 1] > 0) {
                dp[i] = last[a[i] - 1] + 1;
                // 需要找到具体是哪个前驱，这里简化处理
            }
            
            if (dp[i] > 0) {
                if (dp[i] > last[a[i]]) {
                    last[a[i]] = dp[i];
                }
                
                if (dp[i] > max_dp) {
                    max_dp = dp[i];
                    max_pos = i;
                }
            }
        }
    }
    
    // 构造移除方案
    vector<bool> keep(n + 1, false);
    int current = max_pos;
    int expected = a[current];
    
    // 反向追踪保留的积木
    while (current > 0 && expected > 0) {
        if (a[current] == expected) {
            keep[current] = true;
            expected--;
        }
        current--;
    }
    
    // 输出需要移除的积木
    vector<int> to_remove;
    for (int i = 1; i <= n; i++) {
        if (!keep[i]) {
            to_remove.push_back(i);
        }
    }
    
    cout << to_remove.size() << "\n";
    if (!to_remove.empty()) {
        for (int i = 0; i < to_remove.size(); i++) {
            if (i > 0) cout << " ";
            cout << to_remove[i];
        }
        cout << "\n";
    }
    
    return 0;
}

样例分析

输入：

5
1 1 2 5 4

处理过程：

• 积木1：数字1，可以放在位置1，dp[1]=1
• 积木2：数字1，可以放在位置1，但不如积木1优
• 积木3：数字2，可以放在位置2（需要前面有数字1的积木），dp[3]=2
• 积木4：数字5，不可能在正确位置（5>4）
• 积木5：数字4，不可能在正确位置（4>3）

最优保留序列：积木1（位置1，正确），积木3（位置2，正确） 需要移除：积木2,4,5

但样例输出只移除1个积木，说明可能有多个最优解。

总结

本题的关键在于：

1. 理解"正确高度"的重新编号含义
2. 发现最优解中正确积木形成递增序列的性质
3. 使用动态规划 + 数组优化来高效求解

这种"序列重编号+动态规划"的思路在竞赛中很常见，需要仔细理解位置变化的影响。