LeetCode 1626. Best Team With No Conflicts
原题链接
中等
作者:
孤独时代的罗永浩
,
2020-10-18 12:31:48
,
所有人可见
,
阅读 720
贪心 + dp
排序 $O(nlogn)$ dp $O(n^n)$ 总体 $O(n^n)$
1.将所有对应的年纪和分数组成一个pair并按照年龄的升序排序
2.dp: 类似于求最长上升子序列的方法 f[i]表示以位置i结尾,并且选择第i个元素的情况下的最大值
3.状态转移: 因为之前已经按照年龄的升序排序,所以后面人的年龄一定不低于前面人的年龄
则,如果当前人的分数不小于前面人的分数就可以转移,否则不可以
这里先进行排序主要是排除以下情况
age: 2 1 3
sco: 4 1 2
明显age[0]和age[1]可以转移, age[0]和age[2]不可以转移, age[1]和age[2]可以转移。如果不进行排序
那么上述情况age[0]可以以age[1]作为媒介进行转移, 最后结果发生错误
C++ 代码
class Solution {
public:
static bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
vector<pair<int, int>> temp;
for(int i = 0; i < scores.size(); i++)
temp.push_back({ages[i], scores[i]});
sort(temp.begin(), temp.end(), cmp);
vector<int> f(n, 0);
f[0] = temp[0].second;
for(int i = 1; i < n; i++)
{
f[i] = temp[i].second;
for(int j = 0; j < i; j++)
{
if(temp[i].first > temp[j].first && temp[i].second < temp[j].second)
{
continue;
}
else
f[i] = max(f[i], f[j] + temp[i].second);
}
}
int maxv = 0;
for(auto item : f)
{
maxv = max(maxv, item);
}
return maxv;
}
};