1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

本文主要是介绍1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费，

那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w);

考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响，所以还需对f[j]取min j < a[i].e

知道树状数组是可以维护前缀最小值的,那么反转区间，随便维护即可。

c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define lowbit(x) (x & - x)
using namespace std;
typedef long long ll; 
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e5 + 500;const ll inf = 1e16;
int n,s,e;
ll t[N],w; 
struct Str
{int s,e,w;bool operator < (const Str b) const { return s < b.s; }
}a[N];ll query(int x)
{ll z = inf;for(register int i = x ;i ;i -= lowbit(i))z = min (t[i],z) ;return z;
} void update(int x,ll z)
{for(register int i = x ; i <= e ;i += lowbit(i))t[i] = min (t[i],z) ;
} int main()
{read(n);read(s);read(e);s++;e++;rep(i,1,e) t[i] = inf;rep(i,e - s + 2, e) update(i,0);rep(i,1,n) read(a[i].s),read(a[i].e),read(a[i].w);sort(a + 1,a + 1 + n);if(a[1].s > s - 1) return puts("-1"),0;rep(i,1,n)update(e - a[i].e,query(e - a[i].s + 1) + a[i].w); printf("%lld\n",(w = query(1)) == inf ? -1 : w);return 0;
}

这篇关于1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---