题目链接

Leetcode.1626 无矛盾的最佳球队 Rating ： 2027

题目描述

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

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

给你两个列表 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<=10001 <= scores.length, ages.length <= 10001<=scores.length,ages.length<=1000
• scores.length==ages.lengthscores.length == ages.lengthscores.length==ages.length
• 1<=scores[i]<=1061 <= scores[i] <= 10^61<=scores[i]<=106
• 1<=ages[i]<=10001 <= ages[i] <= 10001<=ages[i]<=1000

解法：排序 + dp

先用一个列表 a记录这样的一个二元组 {ages,score}，接着再按 age和 score从小到大排序。

我们定义f(i)f(i)f(i) 代表以 i-1位选手结尾的最大分数。就是必须选择 i-1位选手，而且它是最后一位，能获得的最大分数。

f(i)f(i)f(i)由两部分组成：

• f(i)=a[i].secondf(i) = a[i].secondf(i)=a[i].second

• max(f(j))max(f(j))max(f(j)) (0≤j

时间复杂度：O(n2+nlogn)O(n^2 + nlogn)O(n2+nlogn)

C++代码：

using PII = pair;
class Solution {
public:int bestTeamScore(vector& scores, vector& ages) {int n = scores.size();vector a(n);for(int i = 0;i < n;i++) a[i] = {ages[i],scores[i]};sort(a.begin(),a.end());vector f(n);int ans = 0;for(int i = 0;i < n;i++){f[i] = a[i].second;int d = 0;for(int j = i - 1;j >= 0;j--){if(a[j].second <= a[i].second) d = max(f[j],d);}f[i] += d;ans = max(ans,f[i]);}return ans;}
};