题目大意。N个区间覆盖[T1,T2]及相应的代价S，求从区间M到E的所有覆盖的最小代价是多少。
(1 <= N <= 10,000)。(0 <= M <= E <= 86,399).
思路是DP,首先将每一个区间依照T2从小到大排序，设dp(k)为从m覆盖到k所需最小代价，则有
dp(T2[i]) = min(dp(T2[i]), {dp(j) + Si, T1[i] - 1<=j <= T2[i]}),对于 {dp(j)
+ Si, T1[i] - 1<=j <= T2[i]}我们能够用线段树来进行优化，所以终于复杂度为O(n*logE)。
#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>
#include <time.h>
using namespace std; struct T
{
int t1;
int t2;
int S;
};
#define MAXV 5000000001
long long BinTree[270000];
T cows[10001];
long long DP[86401]; template<class TYPE>
void UpdateValue(TYPE st[],int i, TYPE value, int N, bool bMin)
{
i += N - 1;
st[i] = value;
while (i > 0)
{
i = (i - 1) / 2;
if (bMin)
{
st[i] = min(st[i * 2 + 1], st[i * 2 + 2]);
}
else
st[i] = max(st[i * 2 + 1], st[i * 2 + 2]);
}
} template<class TYPE>
TYPE QueryST(TYPE st[], int a, int b, int l, int r, int k, bool bMin)
{
if (l > b || a > r)
{
return bMin ? MAXV : 0;
}
if (l >= a && b >= r)
{
return st[k];
}
else
{
TYPE value1 = QueryST(st, a, b, l, (r + l) / 2, k * 2 + 1, bMin);
TYPE value2 = QueryST(st, a, b, (r + l) / 2 + 1, r, k * 2 + 2, bMin);
if (bMin)
{
return min(value1, value2);
}
else
{
return max(value1, value2);
}
}
} int compT(const void* a1, const void* a2)
{
if (((T*)a1)->t2 - ((T*)a2)->t2 == 0)
{
return ((T*)a1)->t1 - ((T*)a2)->t1;
}
else
return ((T*)a1)->t2 - ((T*)a2)->t2;
} int main()
{
#ifdef _DEBUG
freopen("e:\\in.txt", "r", stdin);
#endif
int N, M, E;
scanf("%d %d %d", &N, &M, &E);
M++;
E++;
for (int i = 0; i < N; i++)
{
scanf("%d %d %d", &cows[i].t1, &cows[i].t2, &cows[i].S);
cows[i].t1++;
cows[i].t2++;
}
int maxe = 1;
while (maxe < E)
{
maxe *= 2;
}
for (int i = 0; i < maxe * 2;i++)
{
BinTree[i] = MAXV;
}
for (int i = 0; i <= E;i++)
{
DP[i] = MAXV;
} DP[M - 1] = 0;
UpdateValue<long long>(BinTree, M - 1, 0, maxe, true);
qsort(cows, N, sizeof(T), compT);
for (int i = 0; i < N;i++)
{
DP[cows[i].t2] = min(DP[cows[i].t2], QueryST<long long>(BinTree, cows[i].t1 - 1, cows[i].t2, 0, maxe - 1, 0, true) + cows[i].S);
UpdateValue<long long>(BinTree, cows[i].t2, DP[cows[i].t2], maxe, true);
}
if (E <= cows[N - 1].t2)
{
DP[E] = QueryST<long long>(BinTree, E, cows[N - 1].t2, 0, maxe - 1, 0, true);
} if (DP[E] >= MAXV)
{
printf("-1\n");
}
else
printf("%I64d\n", DP[E]);
return 0;
}