原文链接: https://leetcode-cn.com/problems/best-team-with-no-conflicts

英文原文

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.

However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the ith player, respectively, return the highest overall score of all possible basketball teams.

 

Example 1:

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

Example 2:

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

Example 3:

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players. 

 

Constraints:

• 1 <= scores.length, ages.length <= 1000
• scores.length == ages.length
• 1 <= scores[i] <= 106
• 1 <= ages[i] <= 1000

中文题目

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

 

示例 1：

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。

示例 2：

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。

示例 3：

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。

 

提示：

• 1 <= scores.length, ages.length <= 1000
• scores.length == ages.length
• 1 <= scores[i] <= 106
• 1 <= ages[i] <= 1000

通过代码

高赞题解

解题思路

本题的数据范围显然不可能支持我们进行所有子集的枚举。我们希望找到一种顺序，使得我们在进行选择时，总是不会发生冲突。

我们可以将所有队员按照年龄升序进行排序，年龄相同时，则按照分数升序进行排序。排序之后，我们可以进行动态规划。令 $dp[i]$ 表示最后一个队员是第$i$个队员时的最大分数（这里的 $i$ 是重新排序后的编号）。我们只需要在 $[0,i-1]$ 的范围内枚举上一个队员即可。这里，如果上一个队员的分数不超过当前队员的分数，就可以进行转移。

为什么这样的枚举一定是合法的呢？因为我们的最大分数总是在最后一个队员处取得（对于相同年龄的，我们是按照分数升序排序的，所以分数较高的一定在更后面），同时第 $i$ 个队员的年龄不小于之前任意队员的年龄，所以只要第 $i$ 个队员的分数大于等于之前的分组中最后一个队员的分数，就一定可以将第 $i$ 个队员加入到组里，从而得到一个以第 $i$ 个队员为最后一名队员的新的组。

复杂度

• 时间复杂度 $O(N^2)$
• 空间复杂度 $O(N)$

代码

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<int> order(n);
        for (int i = 0; i < n; ++i)
            order[i] = i;
        sort(order.begin(), order.end(), [&](int i, int j){
            return ages[i] < ages[j] || (ages[i] == ages[j] && scores[i] < scores[j]);
        });
        vector<int> dp(n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int idx = order[i];
            dp[i] = scores[idx];
            for (int j = 0; j < i; ++j) {
                int last = order[j];
                if (scores[last] <= scores[idx])
                    dp[i] = max(dp[i], dp[j] + scores[idx]);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

持续更新更多优质题解，欢迎 🌟关注我

统计信息

通过次数	提交次数	AC比率
4070	10478	38.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言