1626. Best Team With No Conflicts
给你很多球员的分数和年龄，要你组建一支总和分数最高的队伍
队伍中球员的分数不能超过任何一个年龄比他大的球员的分数
举例来说，38岁老汉必须是队伍中分数最高的，因为他年纪最大
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.
思路:
1.题目的意思其实就是如果选进的球员照年龄排序的话，他们的分数必须呈非严格递增
也就是对年龄排序之后找一个总和最大的非严格递增的 subsequence
2.找这种 subsequence 相关的就可以用 dp
dp[i] 代表以 score[i] 为结尾的 subsequence 中最大的总和
那对 j > i 如果 score[i] <= score[j] 就代表说以 score[i] 为结尾的 subsequence
在加进 score[j] 后仍会是非严格递增
也就是说就能用 dp[i] 的结果去更新 dp[j]
可以写成 dp[j] = max(dp[j], dp[i] + score[j])
最后就看 dp 中哪个值最大就好 因为最大值不一定会发生在 dp[-1]
Python code:
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
players = list(zip(ages, scores))
players.sort()
n = len(players)
dp = [p[1] for p in players]
res = 0
for i in range(n):
for j in range(i+1, n):
if players[i][1] <= players[j][1]:
dp[j] = max(dp[j], dp[i] + players[j][1])
res = max(res, dp[i])
return res

大师

大师

大师

蛤

大师