1626. 无矛盾的最佳球队

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • LIS
  • 树状数组
  • 线段树
  • 排序

思路

一、问题抽象与等价建模

给定 \(n\) 名球员，每名球员有两个属性：

  • 年龄：\(\text{age}_i\)
  • 分数：\(\text{score}_i\)

球队中任意两名球员 \(i, j\) 不能产生冲突，即不能存在： \[ \text{age}_i < \text{age}_j \;\land\; \text{score}_i > \text{score}_j \] 目标是在无冲突的前提下，选择若干球员，使得分数和最大。

等价约束转化

将球员按某一维度排序后，原问题可转化为一维非下降约束下的最大权值子序列问题。

关键在于选取合适的排序方式，使“无冲突条件”转化为单调约束，从而可用 DP 或数据结构优化。

二、方法一：排序 + 二重动态规划（\(O(n^2)\)）

1. 排序策略

将球员按： \[ (\text{age} \uparrow,\; \text{score} \uparrow) \] 排序。 排序后任意 \(j < i\) 满足： \[ \text{age}_j \le \text{age}_i \] 因此只需保证分数不下降即可避免冲突。

2. 状态定义

令： \[ f[i] = \text{以第 } i \text{ 名球员作为最后一人时的最大团队得分} \] 其中球员编号基于排序后的顺序。

3. 初始状态

每名球员可单独成队： \[ f[i] = \text{score}_i \]

4. 状态转移

枚举前一个球员 \(j < i\)，若满足以下任一条件，则可从 \(j\) 转移到 \(i\)：

  • 年龄相同（同龄无约束）
  • 分数不下降

形式化为： \[ \text{age}_j = \text{age}_i \;\lor\; \text{score}_j \le \text{score}_i \] 转移方程： \[ f[i] = \max \left( f[i],\; f[j] + \text{score}_i \right) \]

5. 答案

\[ \max_{1 \le i \le n} f[i] \]

6. 复杂度分析

  • 时间复杂度：\(\mathcal{O}(n^2)\)
  • 空间复杂度：\(\mathcal{O}(n)\)

7. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        pair<int, int> arr[maxn];
        int n = scores.size();
        for (int i = 0; i < n; ++i)
            arr[i].first = ages[i], arr[i].second = scores[i];
        sort(arr, arr + n);
        int f[maxn];
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            int age = arr[i - 1].first, score = arr[i - 1].second;
            f[i] = score;
            for (int j = i - 1; j >= 1; --j) {
                int x = arr[j - 1].first, y = arr[j - 1].second;
                if (x == age || y <= score)
                    f[i] = max(f[i], f[j] + score);
            }
            res = max(res, f[i]);
        }
        return res;
    }
};

三、方法二：排序 + 树状数组优化 DP（\(O(n \log n)\)）

1. 重新建模思路

改变排序维度，将约束转移到另一属性上。

2. 排序策略

按： \[ (\text{score} \uparrow,\; \text{age} \uparrow) \] 排序。

排序后，在遍历到当前球员时，之前所有球员的分数均不大于当前分数，因此分数约束自动满足。

此时，“无冲突”条件等价于： \[ \text{age}_j \le \text{age}_i \]

3. DP 含义重构

不再显式维护每个球员的 DP 值，而是维护：

“以某个年龄为结尾的最大团队得分”

这正是前缀最大值查询的典型应用场景。

4. 数据结构设计（树状数组）

令 BIT 下标为年龄（\(1 \le \text{age} \le 1000\)）：

  • BIT[a] 表示： 已处理球员中，最后一名球员年龄 ≤ a 的最大团队得分

支持两种操作：

  • 查询前缀最大值： \[ \max_{1 \le k \le a} \text{BIT}[k] \]

  • 单点更新最大值

5. 状态转移

对排序后的每名球员 \((\text{score}, \text{age})\)：

  1. 查询： \[ \text{best} = \max_{k \le \text{age}} \text{BIT}[k] \]

  2. 计算当前 DP： \[ dp = \text{best} + \text{score} \]

  3. 更新： \[ \text{BIT}[\text{age}] = \max(\text{BIT}[\text{age}], dp) \]

6. 初始化说明（关键）

  • BIT 初始全为 0
  • 查询结果为 0 表示“不接任何人”
  • \(dp = \text{score}\) 自然表示“只选自己”

无需显式设置 \(f[i] = \text{score}_i\)。

7. 答案

遍历过程中维护最大 \(dp\)，或最终查询整个 BIT 前缀最大值。

8. 复杂度分析

  • 时间复杂度：\(\mathcal{O}(n \log A)\)，其中 \(A \le 1000\)
  • 空间复杂度：\(\mathcal{O}(A)\)

9. AC代码

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
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int f[maxn] = {}, mx = 0;
    void update(int i, int v) {
        for (; i <= mx; i += i & -i)
            f[i] = max(f[i], v);
    }
    int ask(int i) {
        int res = 0;
        for (; i >= 1; i -= i & -i)
            res = max(res, f[i]);
        return res;
    }
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        vector<pair<int, int>> arr;
        int n = scores.size();
        for (int i = 0; i < n; ++i)
            arr.push_back({scores[i], ages[i]}), mx = max(mx, ages[i]);
        sort(arr.begin(), arr.end());
        int res = 0;
        for (auto& [score, age] : arr) {
            int x = ask(age) + score;
            res = max(res, x);
            update(age, x);
        }
        return res;
    }
};