题意

给出一个时间段\(M\sim E\)，有若干条区间\([l,r]\)覆盖，选择每个区间需要一定代价，求覆盖整个区间的最小代价。
\(0 \leq M \leq E \leq 86399。\)

思路

设\(f_i\)为已经覆盖了\(M \sim i\)用的最小代价。
将每条区间按右端点排序。
可得\(f_{r_i}=min\{f_{l_i-1 \sim r_i}\}+v_i\)，用线段树维护\(min\{f_{l_i-1 \sim r_i}\}\)即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 86400, inf = 707406378;
int n, m, e, ans;
int f[MAXN];

struct node {
	int l, r, v;
} a[10001];

struct segmentTree {
	int dat[MAXN << 2], lazy[MAXN << 2];
	void upload(int p) {
		dat[p] = std::min(dat[p << 1], dat[p << 1 | 1]);
	}
	void download(int p) {
		if (lazy[p] != inf) {
			dat[p << 1] = std::min(dat[p << 1], lazy[p]);
			lazy[p << 1] = std::min(lazy[p], lazy[p << 1]);
			dat[p << 1 | 1] = std::min(dat[p << 1 | 1], lazy[p]);
			lazy[p << 1 | 1] = std::min(lazy[p], lazy[p << 1 | 1]);
			lazy[p] = inf;
		}
	}
	void build(int p, int l, int r) {
		lazy[p] = inf;
		if (l == r) {
			dat[p] = f[l];
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		upload(p);
	}
	int query(int p, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr)
			return dat[p];
		download(p);
		int mid = l + r >> 1;
		int res = inf;
		if (ql <= mid)
			res = std::min(res, query(p << 1, l, mid, ql, qr));
		if (qr > mid)
			res = std::min(res, query(p << 1 | 1, mid + 1, r, ql, qr));
		return res;
	}
	void modify(int p, int l, int r, int ql, int qr, int val) {
		if (ql <= l && r <= qr) {
			dat[p] = std::min(dat[p], val);
			lazy[p] = std::min(lazy[p], val);
			return;
		}
		download(p);
		int mid = l + r >> 1;
		if (ql <= mid)
			modify(p << 1, l, mid, ql, qr, val);
		if (qr > mid)
			modify(p << 1 | 1, mid + 1, r, ql, qr, val);
		upload(p);
	}
}Tree;

int cmp(node x, node y) {
	return x.r < y.r;
}

int main() {
	scanf("%d %d %d", &n, &m, &e);
	m++, e++;
	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].v), a[i].l++, a[i].r++;
	std::sort(a + 1, a + n + 1, cmp);
	memset(f, 127 / 3, sizeof(f));
	for (int i = 0; i < m; i++)
		f[i] = 0;
	Tree.build(1, 1, e);
	for (int i = 1; i <= n; i++) {
		int tmp = a[i].l == 1 ? 0 : Tree.query(1, 1, e, a[i].l - 1, a[i].r);
		if (tmp == 707406378)
			continue;
		f[a[i].r] = (a[i].l == 1 ? 0 : Tree.query(1, 1, e, a[i].l - 1, a[i].r)) + a[i].v, Tree.modify(1, 1, e, a[i].l, a[i].r, f[a[i].r]);
	}
	ans = inf;
	for (int i = a[n].r; i >= e; i--)
		ans = std::min(ans, f[i]);
	if (ans == inf)
		ans = -1;
	printf("%d", ans);
}