文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

假設(shè)你是球隊(duì)的經(jīng)理。對(duì)于即將到來(lái)的錦標(biāo)賽，你想組合一支總體得分最高的球隊(duì)。球隊(duì)的得分是球隊(duì)中所有球員的分?jǐn)?shù) 總和 。

然而，球隊(duì)中的矛盾會(huì)限制球員的發(fā)揮，所以必須選出一支 沒(méi)有矛盾 的球隊(duì)。
如果一名年齡較小球員的分?jǐn)?shù) 嚴(yán)格大于 一名年齡較大的球員，則存在矛盾。同齡球員之間不會(huì)發(fā)生矛盾。

給你兩個(gè)列表 scores 和 ages，其中每組 scores[i] 和 ages[i] 表示第 i 名球員的分?jǐn)?shù)和年齡。

請(qǐng)你返回 所有可能的無(wú)矛盾球隊(duì)中得分最高那支的分?jǐn)?shù) 。

示例 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 名球員。注意，你可以選中多個(gè)同齡球員。示例 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] <= 10^6 1 <= ages[i] <= 1000

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-team-with-no-conflicts
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類(lèi)似題目：

• 動(dòng)態(tài)規(guī)劃應(yīng)用–最長(zhǎng)遞增子序列 LeetCode 300

class Solution {typedef pair<int, int> pii; public:int bestTeamScore(vector<int>& scores, vector<int>& ages) {int n = scores.size();vector<pii> score_Age(n);for(int i = 0; i < n; i++) {score_Age[i] = {scores[i], ages[i]};}sort(score_Age.begin(), score_Age.end(),[&](auto& a, auto& b){return (a.second < b.second || (a.second == b.second && a.first < b.first));});//年齡小的在前，同齡的話，能力小的在前//然后DP尋找上升子序的最大和vector<int> dp(n, 0);dp[0] = score_Age[0].first;int maxscore = dp[0];for(int i = 1; i < n; ++i){int curscore = score_Age[i].first;dp[i] = score_Age[i].first;//初始化為自己的分?jǐn)?shù)for(int j = i-1; j >= 0; j--){int prevscore = score_Age[j].first;if(curscore >= prevscore){ //當(dāng)前人的能力值不是下降的, 加入隊(duì)伍dp[i] = max(dp[i], dp[j]+curscore);}}maxscore = max(maxscore, dp[i]);}return maxscore;} };

184 ms 19 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1626. 无矛盾的最佳球队（最大上升子序DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。