题解 P4644 【[Usaco2005 Dec]Cleaning Shifts 清理牛棚】

· · 题解

数据结构DP做法

P.S: 下面有一篇题解也是数据结构DP，但是代码有一定错误

  • 题目转换：需要令一个区间被完全覆盖，并且令所需代价最小，其中可花费一定代价让一头牛覆盖一个区间。

  • f[i] 表示覆盖从0 ~ i所需要的最小代价
  • c[i].l、c[i].r 表示当前牛可覆盖的区间
  • c[i].salary 表示当前牛所需代价
  • L, R 表示所需要覆盖的区间

转移方程

f[min(c[i].r, r)] = \min_{\max(L - 1, c[i].l - 1)<= j <= \min(R, c[i].r - 1)}{f[j]} + c[i].salary

初值f[L - 1] = 0, 其余为最大值。

意义

表示从当前牛的左端点往前一个点和右端点往前一个点中找一个最小代价点，转移到当前点。

但我们发现，在寻找的过程中明显会超时，所以用一个线段树来维护区间最小值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)
using namespace std;

struct TreeNode {
    int l;
    int r;
    int m;
} t[2100000];

struct Cow {
    int l;
    int r;
    int salary;
    bool operator <(const Cow &c) const {
        return (this -> r) < c.r;
    }
} c[500010];

int n, l, r;
int f[1000010];

void build(int current, int l, int r) {
    t[current].l = l, t[current].r = r;
    if (l == r) {
        t[current].m = f[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(current * 2, l, mid);
    build(current * 2 + 1, mid + 1, r);
    t[current].m = min(t[current * 2].m, t[current * 2 + 1].m);
}

int ask(int current, int l, int r) {
    if (t[current].l == l && t[current].r == r) return t[current].m;
    int mid = (t[current].l + t[current].r) >> 1;
    if (l > mid) return ask(current * 2 + 1, l, r);
    if (r <= mid) return ask(current * 2, l, r);
    return min(ask(current * 2, l, mid), ask(current * 2 + 1, mid + 1, r));
}

void change(int current, int p, const int &value) {
    if (t[current].l == t[current].r) {
        t[current].m = value;
        return;
    }
    int mid = (t[current].l + t[current].r) >> 1;
    if (p > mid) change(current * 2 + 1, p, value);
      else if (p <= mid) change(current * 2, p, value);
    t[current].m = min(t[current * 2 + 1].m, t[current * 2].m);
}

int main() {
    n = read(); l = read(), r = read();
    ++l, ++r;
    for (int i = 0; i < n; ++i) {
        c[i].l = read(), c[i].r = read(), c[i].salary = read();
        ++c[i].l, ++c[i].r;
    }
    memset(f, 0x7f7f7f7f, sizeof(f));
    sort(c, c + n);
    f[l - 1] = 0;
    build(1, l - 1, r);
    int temp, rawR;
    for (int i = 0; i < n; ++i) {
        rawR = min(r, c[i].r);
        temp = f[rawR];
        f[rawR] = min(f[rawR], ask(1, max(c[i].l - 1, l - 1), min(r, c[i].r - 1)) + c[i].salary);
        if (f[rawR] != temp) change(1, rawR, f[rawR]);
    }
    if (f[r] == f[r + 1]) puts("-1");
      else printf("%d\n", f[r]);
    return 0;
}

P.S: 删去了快读, 数组设大了。