挤奶时间milkprod.pas
【问题描述】
贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0..N-1。
Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。
但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。
【输入格式】milkprod.in
第 1 行: 三个整数 N, M, R
第 2..M+1 行: 第 i+1 行 每行三个整数，为Farmer John挤奶计划的开始时间，结束时间，产量。
【输出格式】milkprod.out
一个整数 在 N 个小时内，最大的挤奶的量。
【样例输入】
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31
【样例输出】
43
【问题分析】
本题首先要考虑到的是如何才能安排这些挤奶的时间段，大家都能想到要对这些时间段进行排序，不过在以按哪个“关键字”进行排序时，却有不同的意见了，有的说按开始时间排序，也有的说按结束时间排序，甚至有的还说按挤奶量来排序。可能每个人考虑问题的角度不一样，但我们这里是先要考虑如何安排这些挤奶时间段，所以对于按挤奶量来排序就不大合理了，虽然题目要求是最大的挤奶量。所以这里就要考虑的是按开始时间还是结束时间进行排序呢？其实这两种都应该可以的，我们这里只以按开始时间进行排序来处理。对上述样例，排序后的结果为：
|
序号 |
sTime |
eTime |
Num |
|
1 |
1 |
2 |
8 |
|
2 |
3 |
6 |
24 |
|
3 |
7 |
10 |
31 |
|
4 |
10 |
12 |
19 |
对每个时间段，我们依次来看看若要安排当前时间段挤奶，那获得的奶量是多少呢？
（1）第1个时间段，若要安排这个时间段挤奶的话，显然获得的奶量为8
（2）第2个时间段，若要安排这个时间段挤奶的话，则看看前面所有的挤奶时间段有没有不与它冲突的挤奶时间段（即前面的时间段结束时间(eTime[j])+休息时间(R)<=当前的开始时间(sTime[2])，eTime[j]+R<=Stime[2](1<=j<2)即后面与一样处理），若要则找到一个挤奶量最大的与它组合（这样就是当前时间段挤奶情况下所获得的最大的奶量），这时的挤奶量就是当前时间段的挤奶量(num[i])+能与其它组合时间段的最大挤奶量max(num[j])（即：Num[2] := Num[2] + max(Num[j]) (1<=j<2,后面也是这样来处理）
（3）后面的时间段都同2处理
……
所以得这样一个结论，对于任意一个时间段i，则有if eTime[j] + R <= sTime[i] then Num[i] ß Num[i] + max(num[j]) (其中1<=j<i，max(num[j])表示所有满足能够组合条件中的最大挤奶量)
参考代码段为：
Max := Num[1];
For i := 2 to n do begin
k := 0;
For j := 1 to i – 1 do
if (eTime[j] + R <= sTime[i]) and (k < Num[j]) then k := Num[j];
Num[i] := Num[i] + k;
If max < Num[i] then max := Num[i];
End;