第一次做用线段树维护DP的题目
算是个带权区间覆盖问题（瞎起的名字）
先将所有区间按左端点的升序排序，然后依次枚举
显然可以写出DP方程：
设f[i]表示从要覆盖的区间的左端点(s)到点(i)之间（包括(i)）所有的点全被覆盖所需要的最小花费
f[i] = min(f[i], f[cow[p].s] + cow[p].k), cow[p].s <= i && cow[p].t >= i
其中cow[p].s、cow[p].t分别是第p个区间的左端点和右端点，cow[p].k是代价
当我们选择第p个区间时，应将f[cow[p].s] ~ f[cow[p].t]全部和f[cow[p].s-1] + cow[i].k取最小值
维护区间最小值显然可以线段树，转移时用线段树单点询问
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l+r) >> 1)
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
struct zzz {
int s, t, k;
}cow[100010];
bool cmp(zzz x, zzz y) {
return x.s < y.s;
}
int tree[100010 << 2], tag[100010 << 2];
inline void up(int p) {
tree[p] = min(tree[ls], tree[rs]);
}
inline void down(int p) {
tree[ls] = min(tree[ls], tag[p]); tree[rs] = min(tree[rs], tag[p]);
tag[ls] = min(tag[ls], tag[p]); tag[rs] = min(tag[rs], tag[p]);
tag[p] = 2147483647;
}
void update(int nl, int nr, int k, int l = 0, int r = 86400, int p = 1) {
if(nl <= l && nr >= r) {
tree[p] = min(tree[p], k); tag[p] = min(tag[p], k);
return ;
}
down(p);
if(nl <= mid) update(nl, nr, k, l, mid, ls);
if(nr > mid) update(nl, nr, k, mid+1, r, rs);
up(p);
}
int query(int nl, int nr, int l = 0, int r = 86400, int p = 1) {
if(nl <= l && nr >= r) return tree[p];
down(p);
int ans = 2147483647;
if(nl <= mid) ans = min(query(nl, nr, l, mid, ls), ans);
if(nr > mid) ans = min(query(nl, nr, mid+1, r, rs), ans);
return ans;
}
int main() {
int n = read(), s = read(), t = read();
for(int i = 1; i <= n; ++i) {
int x = read(), y = read(), k = read();
cow[i] = (zzz){x, y, k};
}
sort(cow+1, cow+n+1, cmp);
memset(tree, 127, sizeof(tree)); memset(tag, 127, sizeof(tag));
for(int i = 1; i <= n; ++i) {
if(cow[i].t < s || cow[i].s > t) continue;
if(cow[i].s <= s)
update(cow[i].s, cow[i].t, cow[i].k);
else {
int x = query(cow[i].s-1, cow[i].s-1);
update(cow[i].s, cow[i].t, cow[i].k + x);
}
}
int ans = query(t, t);
if(ans == 2139062143) printf("-1
");
else printf("%d
", ans);
return 0;
}