POJ 3171 Cleaning Shifts 动态规划 + 线段树

一、题目大意

我们有一些个牛棚需要在 [M,E] 的时间区间被清理，题目给出了N（N<=10000）头牛，每头牛对应一个工作时间区间 [t1,t2] 和费用 S。

题目要求计算出 雇佣一些牛 填满 [M,E] 的工作区间，需要的最少费用，如果不能填满 [M,E]的工作区间输出-1。

二、解题思路

不难看出本题目需要用到动态规划，我们可以定义 dp数组，dp[i] 代表填满?[M,i] 这段工作区间需要消耗的最小的费用。最后输出 dp[E] 就是问题的答案。

在起初时，将 dp[M-1]设置为0。其他位置都设置为 INF

然后将 所有的牛按照 区间右边界 t2 排序。

循环每一头牛，进行如下四部操作

1、找出 dp[t1-1] 到 dp[E] 之间最小的值 pre

2、记录当前牛右区间 dp[t2] 的值 crt

3、用 pre + 当前牛的S 得出 nxt

4、如果 nxt < crt，则更新 dp[t2]位置 为nxt。

最终如果dp[E]为 INF，则输出 -1，否则输出 dp[E]的值即可。

不难看出，本题目经常要用计算 某头牛的 [t2 -1 , E] 这段区间内dp数组的最小值，而且常常更新，所以dp数组要用线段树实现，查询最小值的时候直接去 线段树查 [t2 -1 , E+1)的最小值即可，更新值的时候，更新 线段树上的值时将父节点一起更新即可。

（需要注意的一点是，题目初始化的时候，需要将dp[M-1]设置为0，但是题目中说 M>=0，因此可我将本题目所有的数字都往后推1。

在代码中我用 M 代表 M-1，用 E+1代表E，用t2+1代表t2，用t1代表t1-1，所有的区间我都采用左闭右开）

三、代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Node
{
    int t1, t2, s;
    Node(int t1 = 0, int t2 = 0, int s = 0) : t1(t1), t2(t2), s(s) {}
};
ll dat[262144];
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAX_N = 10000;
Node cow[MAX_N];
int n, m, e;
ll query(int _l, int _r, int i, int l, int r)
{
    if (_l >= r || _r <= l)
    {
        return INF;
    }
    else if (l >= _l && r <= _r)
    {
        return dat[i];
    }
    else
    {
        ll lch = query(_l, _r, i * 2 + 1, l, (l + r) / 2);
        ll rch = query(_l, _r, i * 2 + 2, (l + r) / 2, r);
        return min(lch, rch);
    }
}
void update(int x, ll v, int i, int l, int r)
{
    if (x < l || x >= r)
    {
    }
    else if (l == x && r == x + 1)
    {
        dat[i] = v;
        int p = i;
        while (p > 0)
        {
            p = (p - 1) / 2;
            dat[p] = min(dat[p * 2 + 1], dat[p * 2 + 2]);
        }
    }
    else
    {
        update(x, v, i * 2 + 1, l, (l + r) / 2);
        update(x, v, i * 2 + 2, (l + r) / 2, r);
    }
}
bool compare(const Node &a, const Node &b)
{
    return a.t2 < b.t2;
}
void input()
{
    scanf("%d%d%d", &n, &m, &e);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &cow[i].t1, &cow[i].t2, &cow[i].s);
    }
    for (int i = 0; i < 262144; i++)
    {
        dat[i] = INF;
    }
    sort(cow, cow + n, compare);
}
void solve()
{
    update(m, 0LL, 0, 0, e + 2);
    for (int i = 0; i < n; i++)
    {
        ll pre = query(cow[i].t1, e + 2, 0, 0, e + 2);
        ll crt = query(cow[i].t2 + 1, cow[i].t2 + 2, 0, 0, e + 2);
        ll nxt = pre + cow[i].s;
        if (nxt < crt)
        {
            update(cow[i].t2 + 1, nxt, 0, 0, e + 2);
        }
    }
    ll ans = query(e + 1, e + 2, 0, 0, e + 2);
    if (ans == INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%lld\n", ans);
    }
}
int main()
{
    input();
    solve();
    return 0;
}