删数 - 题目列表

题意

给出一排互不相同的正整数。每次可以从左端删掉一段连续数字，或从右端删掉一段连续数字，直到所有数都被删光。

如果本次删掉的是一段 [i, k]：

当只删一个数时，价值就是这个数本身；
当删多个数时，价值是 |x_i-x_k| * (k-i+1)。

要求最大化所有操作价值之和。

思路

最直接的想法是暴力搜索当前删哪一段：如果还剩区间 [l, r]，就枚举本次从左端删掉 [l, k]，或者从右端删掉 [k, r]。

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

static vector<int> a;

long long score(int l, int r) {
    if (l == r) {
        return a[l];
    }
    return 1LL * abs(a[l] - a[r]) * (r - l + 1);
}

long long dfs(int l, int r) {
    if (l > r) {
        return 0;
    }

    long long best = 0;

    // 枚举这一步从左端删掉 [l, k]
    for (int k = l; k <= r; ++k) {
        best = max(best, score(l, k) + dfs(k + 1, r));
    }

    // 枚举这一步从右端删掉 [k, r]
    for (int k = l; k <= r; ++k) {
        best = max(best, dfs(l, k - 1) + score(k, r));
    }

    return best;
}

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

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

    cout << dfs(1, n) << '\n';
    return 0;
}

brute.cpp 按题意完整枚举所有合法删法，显然正确，但复杂度是指数级，只适合小数据对拍。

关键观察是：因为每次都只能从两端删，所以无论删的顺序如何，当前剩下的部分一定始终是原数组中的一个连续区间。于是设 dp[l][r] 表示删光当前区间 [l, r] 的最大总价值。

转移分成两类：

这一步从左端删掉 [l, k]，收益是 score(l, k) + dp[k+1][r]
这一步从右端删掉 [k, r]，收益是 dp[l][k-1] + score(k, r)

其中：

score(i, i) = x_i
score(i, j) = |x_i - x_j| * (j - i + 1)，当 i < j

这张表说明几个典型状态的含义：

状态	表示什么
`dp[3][3]`	只剩第 3 个数时，把它删掉能得到的最大收益
`dp[2][5]`	当前还剩第 2 到第 5 个数时，后续的最大收益
`dp[1][n]`	一开始整段都还在，也就是最终答案

读这张表时，重点是把 dp[l][r] 理解成“当前剩下的一整段”。一旦状态这样定义，每次操作就自然转成“从左删一段”或“从右删一段”两类枚举。

DP 公式

设 $score(l,r)$ 表示一次删掉区间 $[l,r]$ 的收益， $dp_{l,r}$ 表示删光当前区间 $[l,r]$ 的最大总价值。每一步可以从左端删一段，也可以从右端删一段：

dp_{l,r}=\max\left\{ \max_{l\leqslant k\leqslant r}\{score(l,k)+dp_{k+1,r}\}, \max_{l\leqslant k\leqslant r}\{dp_{l,k-1}+score(k,r)\} \right\}

空区间的 $dp$ 值为 $0$ ，最终答案为：

dp_{1,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#include <bits/stdc++.h>
using namespace std;

static long long a[105];
static long long dp[105][105];
static int n;

long long score(int l, int r) {
    if (l == r) {
        return a[l];
    }
    return 1LL * abs(a[l] - a[r]) * (r - l + 1);
}

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

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

    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;

            for (int k = l; k <= r; ++k) {
                long long right_part = (k == r ? 0 : dp[k + 1][r]);
                dp[l][r] = max(dp[l][r], score(l, k) + right_part);
            }

            for (int k = l; k <= r; ++k) {
                long long left_part = (k == l ? 0 : dp[l][k - 1]);
                dp[l][r] = max(dp[l][r], left_part + score(k, r));
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

复杂度

共有 $O(n^2)$ 个区间状态，每个状态要枚举两侧删除长度，所以时间复杂度是 $O(n^3)$ ，空间复杂度是 $O(n^2)$ 。

总结

这题的关键是识别出“删两端”会让剩余部分始终保持为连续区间。抓住这个结构后，就能把暴力搜索改写成标准区间 DP。

一图流解析

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

删数

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析