题解 P4644 【[Usaco2005 Dec]Cleaning Shifts 清理牛棚】
zhylj
·
·
题解
更好体验见博客 https://www.cnblogs.com/zhylj/p/10387852.html
题目
给定 n 个区间 [a_i, b_i], 花费为 c_i, 求覆盖 [L, R] 区间的所有整数的最小花费. 0\le n \le 10^4, 0\le L,R\le 86399
分析
一道很水的题目.
设 f(i) 代表目前选择了第 i 个区间, 且第 i 个区间以前的的所有数都选择到了.
易得:
f(i) = \min_{b_j > a_i, b_i < b_j} f(j) + c_i
一看, 这不就是裸的二维偏序 (其实我并不知道二维偏序的定义是啥).
先把区间按 b_i 排序, 得到:
f(i) = \min_{b_j > a_i} f(j) + c_i
显然有:
b_j > a_i \Rightarrow X-b_j < X-a_i
其中 X 随便取一个较大的值.
发现这个东西只做了单点减少和前缀最小值.
可以用树状数组维护, 时间复杂度 O(R\log n).
### 代码
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int kMaxSize = 1e6 + 5, inf = 0x3f3f3f3f;
int s[kMaxSize + 233], n;
void Modify(int x, int y) {
x = kMaxSize - x;
while(x <= kMaxSize) {
s[x] = std::min(s[x], y);
x += x & -x;
}
}
int Query(int x) {
x = kMaxSize - x;
int ret = inf;
while(x > 0) {
ret = std::min(s[x], ret);
x -= x & -x;
}
return ret;
}
struct Struct {
int a, b, c;
} p[kMaxSize];
bool cmp(Struct x, Struct y) {
return x.b < y.b;
}
int f[kMaxSize], ans = inf;
int main() {
memset(s, 0x3f, sizeof(s));
memset(f, 0x3f, sizeof(f));
int l, r;
scanf("%d%d%d", &n, &l, &r);
for(int i = 1; i <= n; i++)
scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
std::sort(p + 1, p + n + 1, cmp);
for(int i = 1; i <= n; i++) {
if(p[i].a > l) f[i] = Query(p[i].a - 1) + p[i].c;
else f[i] = p[i].c;
Modify(p[i].b, f[i]);
if(p[i].b >= r) ans = std::min(ans, f[i]);
}
if(ans >= inf) printf("-1");
else printf("%d", ans);
return 0;
}
```