鱼C论坛

 找回密码
 立即注册
查看: 2705|回复: 1

[技术交流] C++刷leetcode(1626. 无矛盾的最佳球队)【动态规划】

[复制链接]
发表于 2020-10-23 17:32:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

  2. 然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员,则存在矛盾。同龄球员之间不会发生矛盾。

  3. 给你两个列表 scores 和 ages,其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

  4.  

  5. 示例 1:

  6. 输入:scores = [1,3,5,10,15], ages = [1,2,3,4,5]
  7. 输出:34
  8. 解释:你可以选中所有球员。
  9. 示例 2:

  10. 输入:scores = [4,5,6,5], ages = [2,1,2,1]
  11. 输出:16
  12. 解释:最佳的选择是后 3 名球员。注意,你可以选中多个同龄球员。
  13. 示例 3:

  14. 输入:scores = [1,2,3,5], ages = [8,9,10,1]
  15. 输出:6
  16. 解释:最佳的选择是前 3 名球员。
  17.  

  18. 提示:

  19. 1 <= scores.length, ages.length <= 1000
  20. scores.length == ages.length
  21. 1 <= scores[i] <= 106
  22. 1 <= ages[i] <= 1000

  23. 来源:力扣(LeetCode)
  24. 链接:https://leetcode-cn.com/problems/best-team-with-no-conflicts
  25. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. class Solution {
  2. public:
  3.     int bestTeamScore(vector<int>& scores, vector<int>& ages) {
  4.         priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >temp;
  5.         int len = scores.size();
  6.         for(int i = 0; i < len; i++){
  7.             temp.push(make_pair(scores[i], ages[i]));
  8.         }
  9.         vector<pair<int, int> > store;
  10.         while(!temp.empty()){
  11.             store.push_back(temp.top());
  12.             temp.pop();
  13.         }
  14.         vector<int> dp(len, 0);
  15.         for(int i = 0; i < len; i++){
  16.             dp[i] = store[i].first;
  17.         }
  18.         int res = 0;
  19.         //dp[i]指用新排序的第i个元素作为最后的元素能得到的最大值
  20.         for(int i = 0; i < len; i++){
  21.             for(int j = 0; j < i; j++){
  22.                 if(store[j].second <= store[i].second){
  23.                     dp[i] = max(dp[i], dp[j] + store[i].first);
  24.                 }
  25.                
  26.             }
  27.             res = max(res, dp[i]);
  28.         }
  29.         return res;
  30.     }
  31. };
复制代码

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-10-23 17:34:22 | 显示全部楼层
先排序再使用动态规划
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-1 16:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表