排序 + 动态规划
两个性质: ①得分最高 ② 年龄大的,分数要高。
这提示我们按照分数,或者年龄,对列表排序。先固定一个性质,才考虑另外的性质。
按照分数和年龄排序都可以。这里按照年龄,从大到小排序。年龄大的,自然在前;年龄相同,分数大的在前。在排序后的数组里,找到最大下降子序列和,满足一个条件 —— 越靠前,分数越大。即为所求。
状态定义: f[i]f[i]f[i] 表示所有以 p[i]p[i]p[i] 结尾的最大下降子序列和。
状态转移方程: f[i]=max(f[j])+p[i],j∈[0,i)f[i] = max(f[j]) +p[i], \ j \isin [0,i)f[i]=max(f[j])+p[i], j∈[0,i)
最后,答案序列不一定以数组末尾结尾,可能在任何位置结尾,需要维护最大的 f[i]f[i]f[i] ,即为答案。
class Solution {
public:static bool cmp(pair<int, int> x, pair<int, int> y) {return (x > y);}int bestTeamScore(vector<int>& scores, vector<int>& ages) {int n = scores.size();vector<pair<int, int>> p(n);for (int i = 0; i < n; i ++) p[i] = {ages[i], scores[i]};sort(p.begin(), p.end(), cmp);vector<int> f(n);int ans = 0;for (int i = 0; i < n ; i ++) {for (int j = i - 1; j >= 0; j --) {if (p[j].second >= p[i].second) {f[i] = max(f[i], f[j]);}}f[i] += p[i].second;ans = max (ans, f[i]);}return ans;}
};
- 时间复杂度 : O(n2)O(n ^ 2)O(n2) , nnn 是球员的数目,一共 nnn 状态,平均每个状态转移 nnn 次,时间复杂度 O(n2)O(n^2)O(n2)。
- 空间复杂度 : O(n)O(n)O(n) ,状态数组和分数-年龄数组的空间复杂度 O(n)O(n)O(n) 。
AC
致语
- 理解思路很重要
- 读者有问题请留言,清墨看到就会回复的。