- 题目描述:
-
小明每天都在开源社区上做项目,假设每天他都有很多项目可以选,其中每个项目都有一个开始时间和截止时间,假设做完每个项目后,拿到报酬都是不同的。由于小明马上就要硕士毕业了,面临着买房、买车、给女友买各种包包的鸭梨,但是他的钱包却空空如也,他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明,如何在最短时间内安排自己手中的项目才能保证赚钱最多(注意:做项目的时候,项目不能并行,即两个项目之间不能有时间重叠,但是一个项目刚结束,就可以立即做另一个项目,即项目起止时间点可以重叠)。
- 输入:
-
输入可能包含多个测试样例。
对于每个测试案例,输入的第一行是一个整数n(1<=n<=10000):代表小明手中的项目个数。接下来共有n行,每行有3个整数st、ed、val,分别表示项目的开始、截至时间和项目的报酬,相邻两数之间用空格隔开。st、ed、value取值均在32位有符号整数(int)的范围内,输入数据保证所有数据的value总和也在int范围内。
- 输出:
-
对应每个测试案例,输出小明可以获得的最大报酬。
- 样例输入:
-
31 3 64 8 92 5 1641 14 105 20 1515 20 818 22 12
- 样例输出:
-
1622
动态规划,先按项目结束时间排序,用数组a[]来存储如果安排第i个项目时所得的最大收益。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 struct proj { 8 int st; 9 int ed;10 int val;11 };12 13 bool cmp(const proj &p1, const proj &p2) {14 return p1.ed < p2.ed;15 }16 17 int main() {18 //freopen("input.txt", "r", stdin);19 int n;20 while (cin >> n) {21 vector v;22 proj p;23 p.st = 0;24 p.ed = 0;25 p.val = 0;26 v.push_back(p);27 int *a = new int[n+1];28 int i, j;29 for (i = 1; i <= n; ++i) {30 cin >> p.st >> p.ed >> p.val;31 v.push_back(p);32 a[i] = 0;33 }34 sort(v.begin(), v.end(), cmp);35 a[0] = 0;36 a[1] = v[1].val;37 for (i = 2; i <= n; ++i) {38 for (j = i - 1; j > 0; --j) {39 if (v[i].st >= v[j].ed) 40 break;41 }42 a[i] = a[j] + v[i].val;43 a[i] = a[i] > a[i-1] ? a[i] : a[i-1];44 }45 cout << a[n] << endl;46 }47 return 0;48 }