LeetCode 1626. 无矛盾的最佳球队（最大上升子序DP）

示例 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^6
1 <= ages[i] <= 1000

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;//初始化为自己的分数
            for(int j = i-1; j >= 0; j--)
            {
                int prevscore = score_Age[j].first;
                if(curscore >= prevscore)
                {   //当前人的能力值不是下降的, 加入队伍
                    dp[i] = max(dp[i], dp[j]+curscore);
                }
            }
            maxscore = max(maxscore, dp[i]);
        }
        return maxscore;
    }
};