LeetCode 1626. 无矛盾的最佳球队
原题链接
中等
作者:
α_29
,
2023-03-22 19:05:26
,
所有人可见
,
阅读 138
排序+dp
数组2限制的情况下 数组1求最值
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
vector<pair<int,int>> all(n);
for(int i = 0 ; i < n ; i ++ )
all[i] = {scores[i],ages[i]};
sort(all.begin(),all.end());
int f[n];//f[i]表示以第i个人结尾的最大值
memset(f,0,sizeof f);
int res = 0;
for(int i = 0; i < n ; i ++ ){
f[i] = all[i].first;
for(int k = 0; k < i ; k ++ ){
if(all[i].second >= all[k].second )
f[i] = max(f[i],f[k] + all[i].first);
}
res = max(res,f[i]);
}
return res;
}
};
优化
排序+树状数组
待学..