lc1626
//双升sort后lis dp
for (int j = 0; j < i; j++)
//if condition
dp[i] = max(dp[i],dp[j] + as[i].second);
class Solution {
typedef pair<int, int> pii;
//sort后lis dp
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = ages.size();
vector<pii> as;
for (int i = 0; i < n; i++) {
as.push_back({ages[i], scores[i]});
}
sort(as.begin(), as.end(), [](const pii& a, const pii& b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});//双升
vector<int> dp(n);
int max_score = 0;
for (int i = 0; i < n; i++) {
dp[i] = as[i].second; //init
// 年龄≤当前且分数≤当前的，累加最大得分
for (int j = 0; j < i; j++) {
if (as[j].second <= as[i].second) {
dp[i] = max(dp[i],dp[j] + as[i].second);
}
}
max_score = max(max_score, dp[i]);
}
return max_score;
}
};
优雅的idx写法
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n=ages.size(),ans=0;
vector<int> index(n),dp(n);//下标数组和dp数组
iota(index.begin(),index.end(),0);//index赋值为0~n-1
sort(index.begin(),index.end(),[&](int i,int j){return ages[i]==ages[j]?scores[i]<scores[j]:ages[i]<ages[j];});//先按年龄升序，再按分数升序进行排序
for(int i=0;i<n;++i)//递推过程
{
int res=0;
for(int j=0;j<i;++j)
if(scores[index[i]]>=scores[index[j]])//满足约束，进行保留
res=max(res,dp[j]);
dp[i]=res+scores[index[i]],ans=max(ans,dp[i]);//得到dp[i]，并维护ans
}
return ans;
}
};
