题意
给出一个时间段\(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);
}