Python程式：查詢無衝突的最佳團隊

假設我們有兩個列表，分別稱為 scores 和 ages，其中 scores[i] 和 ages[i] 分別表示籃球比賽中第 i 位球員的分數和年齡。我們想要選擇總得分最高的團隊。這裡團隊的分數是團隊中所有球員分數的總和。但我們不允許比賽中有衝突。如果較年輕的球員得分嚴格高於較年長的球員，則存在衝突。

因此，如果輸入類似 scores = [5,7,9,14,19]，ages = [5,6,7,8,9]，則輸出將為 54，因為我們可以選擇所有球員。

為了解決這個問題，我們將遵循以下步驟：

• sa := 透過分別從 ages 和 scores 中獲取元素 a 和 s，形成一個對列表
• 對列表 sa 進行排序
• scores := 從 sa 中建立一個分數列表
• maxScore := 0
• n := scores 的大小
• dp := 一個長度為 n 的陣列，並填充為 0
• 對於 i 從 0 到 n - 1，執行以下操作：
  • score := scores[i]
  • dp[i] := score
  • 對於 j 從 0 到 i - 1，執行以下操作：
    • 如果 scores[j] <= score，則
      • dp[i] := dp[i] 和 dp[j] + score 的最大值
  • maxScore := maxScore 和 dp[i] 的最大值
• 返回 maxScore

示例

讓我們看看以下實現以獲得更好的理解：

def solve(scores, ages):
   sa = [[a,s] for a,s in zip(ages,scores)]

   sa.sort()
   scores = [s for a,s in sa]

   maxScore = 0
   n = len(scores)
   dp = [0] * n

   for i in range(n):
      score = scores[i]
      dp[i] = score

      for j in range(i):
         if scores[j] <= score:
            dp[i] = max(dp[i],dp[j] + score)
      maxScore = max(maxScore, dp[i])

   return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))

輸入

[5,7,9,14,19], [5,6,7,8,9]

輸出

54

Arnab Chakraborty

更新於: 2021年10月5日

438 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習