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]了。