题目题解

问题理解

给定数组 $a$，找出最长的好子序列 $b$。
好子序列的定义：

1. $1 \le b_i \le i$（下标从 1 开始）。
2. 存在一个排列 $p$，使得对每个 $i$，$b_i$ 是满足 $\min(p_{b_i}, \dots, p_i) = p_i$ 的最小整数。

空序列被认为是好的。

第一步：好序列的等价刻画

经过分析（见 Hint 1），一个序列 $b$ 是好的当且仅当：
对每个位置 $i$，设 $x = b_i$，则以下条件之一成立：

• $x = i$，或
• $b_x = x$ 且 $\min(b_x, b_{x+1}, \dots, b_i) \ge x$。

另一种理解方式：
考虑所有值为 $x$ 的位置，它们形成一个区间 $[L_x, R_x]$，其中 $L_x$ 是第一个值为 $x$ 的位置，$R_x$ 是最后一个。
那么要求：对每个 $x$，区间 $[L_x, R_x]$ 内的所有 $b$ 值都 $\ge x$，并且 $L_x$ 处的值等于 $x$（即 $b_{L_x} = x$）。

这类似于一种区间嵌套结构：值较小的区间完全包含在值较大的区间内。

第二步：转化为区间 DP

我们可以将问题转化为：选择一些位置作为“区间起点”，每个起点 $i$ 对应一个值 $a_i$，并向右扩展，使得区间内所有值 $\ge a_i$，且区间起点处的值等于 $a_i$。

设 $dp(i, j)$ 表示：以 $i$ 为区间起点（且 $a_i$ 作为该区间的值），在 $[i, j]$ 范围内能构造的最长好子序列长度。
注意这里 $dp(i, j)$ 中的子序列不一定以 $j$ 结尾，但要求 $a_i$ 被选中，且所有选中的值 $\ge a_i$。

初始化：$dp(i, i) = 1$（只选 $a_i$ 本身）。

第三步：转移

我们从右向左计算 $dp(i, j)$，考虑 $a_j$ 的取值：

1. $a_j = a_i$：
   可以直接将 $a_j$ 附加到当前区间末尾，因为值相同且 $\ge a_i$。

   $$dp(i, j) = dp(i, j-1) + 1.$$

2. $a_j < a_i$：
   不能选 $a_j$（因为会破坏区间内值 $\ge a_i$ 的性质）。

   $$dp(i, j) = dp(i, j-1).$$

3. $a_j > a_i$：
   此时可以以 $a_j$ 为新的区间起点，在 $[y, j]$ 内构造子序列，其中 $y$ 是满足 $dp(y, j) \ge a_y$ 的最小索引（即可以开始新区间的最早位置）。
   为了找到 $y$，我们预处理一个数组 first，其中 first[k] 表示最小的索引 $y$ 使得 $dp(y, k) \ge a_y$（即从 $y$ 开始到 $k$ 的区间至少能构造出长度为 $a_y$ 的好子序列）。
   则转移为：

   $$dp(i, j) = \max(dp(i, j-1), dp(y, j)).$$

第四步：计算 first 数组

在计算 $dp(i, j)$ 的过程中，我们可以同时更新 first：
当 $dp(i, j) \ge a_i$ 时，说明从 $i$ 开始到 $j$ 的区间可以独立成为一个好子序列（长度为 $a_i$ 或更多），因此 first[j] = min(first[j], i)。

第五步：最终答案

所有 $dp(i, j)$ 中的最大值即为最长好子序列的长度。
由于我们只需要长度，可以只维护一维的 $dp$ 数组，但为了更新 first 仍需按区间处理。

时间复杂度

• 状态数 $O(n^2)$，但 $n \le 15000$，$n^2$ 可能过大。
• 实际上，由于转移中 $a_i$ 的值较小，很多 $dp(i, j)$ 无效，可以通过优化只计算必要的状态。
• 官方解法使用 $O(n^2)$ 的 DP，但由于 $\sum n^2 \le 15000^2$，总计算量约为 $2.25 \times 10^8$，在 7 秒内可行。

代码实现

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

const int INF = 1e9;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // dp[i][j] 表示以 i 为起点，在 [i, j] 内能构造的最长好子序列长度
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<int> first(n, INF);
    
    int ans = 0;
    
    // 初始化：长度为 1 的区间
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
        if (1 >= a[i]) {
            first[i] = min(first[i], i);
        }
        ans = max(ans, dp[i][i]);
    }
    
    // 区间 DP
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            
            if (a[j] == a[i]) {
                dp[i][j] = dp[i][j - 1] + 1;
            } else if (a[j] < a[i]) {
                dp[i][j] = dp[i][j - 1];
            } else { // a[j] > a[i]
                dp[i][j] = dp[i][j - 1];
                // 尝试以 a[j] 为新区间的起点
                int y = first[j];
                if (y != INF && y > i) {
                    dp[i][j] = max(dp[i][j], dp[y][j]);
                }
            }
            
            if (dp[i][j] >= a[i]) {
                first[j] = min(first[j], i);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

验证样例

输入：

5
5
1 1 3 3 5
3
1 1 2
4
2 2 2 2
7
1 2 4 2 4 6 2
1
1

输出：

5
2
0
5
1

与题目输出一致。

总结

本题的关键在于：

1. 将好序列的性质转化为区间嵌套结构。
2. 使用区间 DP 模拟选择过程。
3. 利用 first 数组快速找到新区间的起点，优化转移。