1027 带权活动选择

た 入场券 2022-09-12 00:57 236阅读 0赞

Description

  1. 给定n个活动，活动ai表示为一个三元组(si,fi,vi)，其中si表示活动开始时间，fi表示活动的结束时间，vi表示活动的权重,
  2. si<fi。带权活动选择问题是选择一些活动，使得任意被选择的两个活动ai和aj执行时间互不相交，即区间[si,fi)与[sj,fj)
  3. 互不重叠，并且被选择的活动的权重和最大。请设计一种方法求解带权活动选择问题。

Input

  1. 第一行输入M(M<=10)表示有M组数据。每组数据输入整数N(N<=10000), 接下来输入N个活动。

Output

  1. 输出M行正整数，第i行表示第i组数据的能够选择活动最大权值和。

Sample Input

  1. 2
  2. 5
  3. 7 9 9
  4. 7 8 1
  5. 6 7 9
  6. 6 8 5
  7. 4 9 9
  8. 5
  9. 4 7 9
  10. 3 4 4
  11. 7 8 8
  12. 8 9 6
  13. 4 5 9

Sample Output

  1. 18
  2. 27

发表评论

表情：
评论列表 （有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

    相关 活动选择

    Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现

    电玩女神电玩女神/ 0 赞/ 231 阅读

    相关 带权重值的随机选择算法

    一个新的功能上线都会走灰度的过程，万一新功能有问题，则会导致线上的大量的报错，甚至不可用的严重情况。比如我们现在本来接入了2个短信渠道去发送短信，现在接入好了第三个渠道，如果我

    野性酷女野性酷女/ 0 赞/ 208 阅读

    相关 活动选择

    活动选择 Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后

    亦凉亦凉/ 0 赞/ 207 阅读

    相关 活动选择

    活动选择 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 学校的大学生艺术中心周日将面

    墨蓝墨蓝/ 0 赞/ 284 阅读