动态规划——带权活动选择

带权活动选择
Time Limit: 3000 MS		Memory Limit: 1000 KB

Description

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

Input

第一行输入M(M<=10)表示有M组数据。每组数据输入整数N(N<=10000), 接下来输入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;
}