USACO05DEC Cleaning Shifts

题目传送门

第一次做用线段树维护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\n");
    else printf("%d\n", ans);
    
    return 0;
}

USACO05DEC Cleaning Shifts

原文：https://www.cnblogs.com/morslin/p/11855890.html