Language:
Cleaning Shifts
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2093 Accepted: 735
Description
有N （1 <= N <= 10,000）个区间，求覆盖[M,E]（0 <= M <= E <= 86,399）的最小代价。
每个区间的代价为S （where 0 <= S <= 500,000）。
Input
第一行3个整数： N, M, E.
第二行到第n+1行，每行3个数，分别表示第i-1个区间的左端点T1,右端点T2,和代价S.
Output www.2cto.com
仅一行表示最小代价，无解输-1.
Sample Input
3 0 4
0 2 3
3 4 2
0 0 1
Sample Output
5
Hint
样例解释
取第一个和第二个区间。
Source
USACO 2005 December Silver
这题是一个Dp问题，先列出Dp方程。
F[i]表示取[M,i]这个区间的代价
显然F[M-1]=0,答案就是F[E]
则方程为F[a[i].T2]=min（F[j]）+a[i].S （T1-1<=J<=T2-1）
a[i]按T2从小到大排列；
那么显然a[i]取时，[M,T1-1]已经被前面的给取了，
因为如果被后面的[t1,t2] 取了，那么必有t1<T1 T2<t2, 就没必要取[T1,T2]了。