北京外贸网站建设公司,一流的镇江网站优化,网站服务器送一年,广州励网网站建设网络公司带权活动选择Time Limit: 3000 MSMemory Limit: 1000 KB
Description
给定n个活动#xff0c;活动ai表示为一个三元组(si,fi,vi)#xff0c;其中si表示活动开始时间#xff0c;fi表示活动的结束时间#xff0c;vi表示活动的权重,
sifi。带权活动选择问题是选择一些活…带权活动选择Time Limit: 3000 MSMemory Limit: 1000 KB
Description
给定n个活动活动ai表示为一个三元组(si,fi,vi)其中si表示活动开始时间fi表示活动的结束时间vi表示活动的权重,
sifi。带权活动选择问题是选择一些活动使得任意被选择的两个活动ai和aj执行时间互不相交即区间[si,fi)与[sj,fj)
互不重叠并且被选择的活动的权重和最大。请设计一种方法求解带权活动选择问题。
Input
第一行输入M(M10)表示有M组数据。每组数据输入整数N(N10000), 接下来输入N个活动。
Output
输出M行正整数第i行表示第i组数据的能够选择活动最大权值和。
Sample Input
2
5
7 9 9
7 8 1
6 7 9
6 8 5
4 9 9
5
4 7 9
3 4 4
7 8 8
8 9 6
4 5 9
Sample Output
18
27
二、解题思路
先将活动按照结束时间进行排序
三、代码示例
注意这里使用了sort函数进行排序sort
#include iostream
#include algorithm
using namespace std;struct Activity {
int s, e, v;
};bool cmp(Activity a, Activity b) { return a.e b.e;
}int main() {int m, n;cin m;while (m--) {cin n;int dp[10001] { 0 };Activity activities[10001];for (int i 1; i n; i) {cin activities[i].s;cin activities[i].e;cin activities[i].v;}dp[0] 0;activities[0].s activities[0].e activities[0].v 0;sort(activities 1, activities n 1, cmp);for (int i 1; i n; i) {for (int j i - 1; j 0; j--) {//从前一个开始依次向前找结束时间在它开始时间之前的if (activities[j].e activities[i].s) {dp[i] max(dp[i - 1], dp[j] activities[i].v);break;}}}cout dp[n] endl;}return 0;
}
