本文涉及知識點

C++動態規劃 離散化

LeetCode1626. 無矛盾的最佳球隊

假設你是球隊的經理。對于即將到來的錦標賽，你想組合一支總體得分最高的球隊。球隊的得分是球隊中所有球員的分數 總和 。
然而，球隊中的矛盾會限制球員的發揮，所以必須選出一支 沒有矛盾 的球隊。如果一名年齡較小球員的分數 嚴格大于 一名年齡較大的球員，則存在矛盾。同齡球員之間不會發生矛盾。
給你兩個列表 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 <= 1000
scores.length == ages.length
1 <= scores[i] <= 10⁶
1 <= ages[i] <= 1000

動態規劃+離散化

將分數離散化，并用nums記錄原始分數。分數最小的位1,次小的為2$?$ 。
將年齡離散化，方便處理比當前隊員年齡小的隊員。

動態規劃的狀態表示

dp[i][j] 表示 球員的年齡 <= i，離散化后的能力 <=j 組成的無矛盾球隊的最大得分。空間復雜度：O(nm) m是離散后的最大年齡

動態規劃的填表順序

將任意最優解，按如下方式排序后，仍然是最優解。
一，年齡小的在前，年齡大的在后。
二，年齡相等，能力小的在前，能力大的在后。
三，年齡能力都相等，按scores中的順序。
indexs的球員的下標按上述方式排序，按k:indexs順序處理各球員。

動態規劃的轉移方程

i = ages[k] j = scores[k]
$$dp[i][j]=Max\{\begin{array}{llc}dp[i][j]+當前球員的能力& & 前一個球員年齡相同\\ dp[i?1][j]+當前球員的能力& & 前一個球員年齡不同\end{array}$$
每次更新dp后，都要：

for (j =1 ; j <= N; j++) {dp[i][j] = max(dp[i][j], dp[i][j - 1]);dp[i][j] = max(dp[i][j], dp[i-1][j ]);}

時間復雜度：O(nm)

動態規劃的初始值

全為0

動態規劃的返回值

dp的最大值。

代碼

核心代碼

class Solution {public:int bestTeamScore(vector<int>& scores, vector<int>& ages) {const int N = scores.size();{auto tmp = ages;tmp.emplace_back(0);CDiscretize dis(tmp);for (auto& i : ages) {i = dis[i];}}const int M = *max_element(ages.begin(), ages.end());auto tmp = scores;tmp.emplace_back(0);CDiscretize dis(tmp);for (auto& i : scores) {i = dis[i];}vector<int> index(N);iota(index.begin(), index.end(), 0);sort(index.begin(), index.end(), [&](int i1, int i2) {return (ages[i1] < ages[i2]) || ((ages[i1] == ages[i2]) && (scores[i1] < scores[i2]));	});vector<vector<int>> dp(M + 1, vector<int>(N + 1));int ans = 0;for (int k : index) {const int i = ages[k];int j = scores[k];dp[i][j] = max(dp[i - 1][j], dp[i][j]) + dis.m_nums[j];ans = max(ans, dp[i][j]);for (j =1 ; j <= N; j++) {dp[i][j] = max(dp[i][j], dp[i][j - 1]);dp[i][j] = max(dp[i][j], dp[i-1][j ]);}}return ans;}};

單元測試

vector<int> scores, ages;TEST_METHOD(TestMethod1){scores = { 3,2,4 }, ages = { 1,2,3 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(7, res);}TEST_METHOD(TestMethod11){scores = { 1,3,5,10,15 }, ages = { 1,2,3,4,5 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(34, res);}TEST_METHOD(TestMethod12){scores = { 4,5,6,5 }, ages = { 2,1,2,1 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(16, res);}TEST_METHOD(TestMethod13){scores = { 1,2,3,5 }, ages = { 8,9,10,1 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(6, res);}TEST_METHOD(TestMethod14){scores = { 1,1,1 }, ages = { 3,2,1 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(3, res);}TEST_METHOD(TestMethod15){scores = { 1,1,1 }, ages = { 1,3,5};auto res = Solution().bestTeamScore(scores, ages);AssertEx(3, res);}TEST_METHOD(TestMethod16){scores = { 1,1,1,1,1,1,1,1,1,1 }, ages = { 811,364,124,873,790,656,581,446,885,134 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(10, res);}TEST_METHOD(TestMethod17){scores = { 6,5,1,7,6,5,5,4,10,4 }, ages = { 3,2,5,3,2,1,4,4,5,1 };auto res = Solution().bestTeamScore(scores, ages);AssertEx(43, res);}

優化

i1 < i2 ，k1 = index[i1] ,k2 = index[i2]。
某方案以球員k1結尾。
如果k1的能力小于等于k2，則此方案加上i2一定不會沖突。
如果 k1的能了大于k2，由于已經按本題解排序，所以k1的年齡一定小于k2：故一定沖突。
故只需枚舉能力小于等于當前能力的球員。空間復雜度：O(n)
可以用線段樹。時間復雜度：O(nlogn)
直接枚舉時間復雜度：O(nn)

代碼

class CDiscretize //離散化
{
public:CDiscretize(vector<int> nums){sort(nums.begin(), nums.end());nums.erase(std::unique(nums.begin(), nums.end()), nums.end());m_nums = nums;for (int i = 0; i < nums.size(); i++){m_mValueToIndex[nums[i]] = i;}}int operator[](const int value)const{auto it = m_mValueToIndex.find(value);if (m_mValueToIndex.end() == it){return -1;}return it->second;}int size()const{return m_mValueToIndex.size();}vector<int> m_nums;
protected:	unordered_map<int, int> m_mValueToIndex;
};class Solution {public:int bestTeamScore(vector<int>& scores, vector<int>& ages) {const int N = scores.size();			CDiscretize dis(scores);for (auto& i : scores) {i = dis[i];}vector<int> index(N);iota(index.begin(), index.end(), 0);sort(index.begin(), index.end(), [&](int i1, int i2) {return (ages[i1] < ages[i2]) || ((ages[i1] == ages[i2]) && (scores[i1] < scores[i2]));	});vector<int> dp(N + 1);int ans = 0;for (int k : index) {const int i = ages[k];int j = scores[k];const int iMax = *max_element(dp.begin() , dp.begin() + j + 1);dp[j] = max(dp[j], iMax + dis.m_nums[j]);ans = max(ans, dp[j]);}return ans;}};

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功 成功+反思=成功

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。