数列 - 题目列表

题意

给出一个长度为 n 的序列。

你可以删除若干个数，剩下的数重新组成一个新序列。要求让新序列里“数值等于自己新位置”的元素尽量多，求这个最大值。

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include <bits/stdc++.h>
using namespace std;

// brute.cpp：枚举删还是不删，直接构造剩余序列并统计有多少个数等于它的新位置。

const int MAXN = 25;

int n;
int a[MAXN];
int ans;
vector<int> cur;

void dfs(int idx) {
    if (idx > n) {
        int cnt = 0;
        for (int i = 0; i < (int)cur.size(); i++) {
            if (cur[i] == i + 1) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
        return;
    }

    // 删除 a[idx]
    dfs(idx + 1);

    // 保留 a[idx]
    cur.push_back(a[idx]);
    dfs(idx + 1);
    cur.pop_back();
}

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

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

    ans = 0;
    dfs(1);

    cout << ans << '\n';
    return 0;
}

brute.cpp 会枚举每个元素删还是不删，构造最终子序列后，再统计有多少个位置满足 value = position。

这个做法非常直观，但一共有 2^n 种删法，显然不可能直接使用。

关键在于不要盯着“删哪些数”，而是只盯着：

哪些元素最终会成为匹配点

假设原数组中 a[j] 和 a[i]（j < i）都想成为匹配点。

那它们在最终序列里的位置必须分别是：

a[j]
a[i]

所以它们之间在最终序列里必须隔出：

a[i] - a[j] - 1 个位置

而原数组中它们之间一共只有：

i - j - 1 个元素

可供保留来填这些位置，因此必须满足：

i - j >= a[i] - a[j]

同时，因为后一个匹配点的位置更靠后，所以还必须有：

a[j] < a[i]

另外，a[i] 自己想成为匹配点，前面至少要有 a[i]-1 个保留下来的元素，因此还要满足：

a[i] <= i

于是设：

dp[i] 表示把 a[i] 作为最后一个匹配点时，最多能得到多少个匹配点

若 a[i] <= i，它可以单独成为第一个匹配点，初始化 dp[i] = 1。

然后枚举 j < i：

若 a[j] < a[i]
且 i - j >= a[i] - a[j]

就可以转移：

dp[i] = max(dp[i], dp[j] + 1)

条件表

这张表展示两个匹配点能否相连时要检查的条件：

条件	含义
`a[j] < a[i]`	后一个匹配点必须占据更靠后的位置
`i - j >= a[i] - a[j]`	原数组中有足够多的元素来填满中间位置差

DP 公式

设 $dp_i$ 表示把 $a_i$ 作为最后一个匹配点时，最多能得到多少个匹配点。若 $a_i\leqslant i$ ，则：

dp_i\geqslant 1

当 $j<i$ ，且两个匹配点能相连：

a_j<a_i,\quad i-j\geqslant a_i-a_j

就可以转移：

dp_i=\max(dp_i,\ dp_j+1)

最终答案为：

\max_i dp_i

公式解释：只要确定哪些元素成为匹配点，就不必关心其他被保留元素的具体选择。两个匹配点能相连，要求目标位置差不超过原数组位置差，这样中间才有足够元素填空。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int a[MAXN];
int dp[MAXN]; // dp[i]：把 a[i] 作为最后一个“在自己位置上的数”时，最多能有多少个这样的数

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

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

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] <= i) {
            dp[i] = 1;
        }

        for (int j = 1; j < i; j++) {
            // 让 a[j] 和 a[i] 都成为匹配点时，
            // 中间必须有足够多的元素来填满位置差。
            if (dp[j] > 0 && a[j] < a[i] && i - j >= a[i] - a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

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

总结

这题的关键是把“删除方案”转成“匹配点之间是否能连起来”。

一旦看出中间需要满足“原数组位置差不少于目标位置差”，整题就变成了一个很干净的以 i 结尾的 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

数列

目录

题意

思路

条件表

DP 公式

代码

复杂度

总结

一图流解析