本文主要是介绍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;
}这篇关于POJ 3171 Cleaning Shifts 动态规划 + 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
