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

· · 题解

线段树维护优化DP裸题。

首先，题目变量名取得十分奇特，所以我们约定：开始时间由M变为B，每个奶牛的花费由S变为cost，时间段总长为L

另外,文中的|是集合的符号不是 or 运算哈

按照普通的DP思路，设f[i]为从M到i的最小花费，每个时间段更新都扫一次，复杂度O(N*L)，肯定是过不了的。

然后我们发现，每个时间段都扫一遍性价比是很低的，因为如果我们不更新(f[j]>f[i]|j<i)，那么每个奶牛只会做一次贡献，所以我们直接按t2排序，则DP时，f[t2[i]]=min(f[t2[i]],min(f[x]|t1[i]-1<x<t2[i])+cost[i])

显然，这个min里面的东西是可以用线段树维护的。

然后就O(n{log_2}n)了，常数挺小，思路简单，感觉不用过多解释了

代码细节&解释

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MN 25005
#define INF 2147483647777
#define Ls (nod<<1)
#define Rs (nod<<1|1)
#define mid ((l+r)>>1)
struct data{
    int t1,t2,cost;
}w[MN];
int n,b,e;
LL f[MN<<4],ans[MN<<2];
//f：线段树中的答案 ans:从L到i的答案
inline LL min(int a,int b){
    return a<b?a:b;
}
inline bool cmp(data a,data b){
    return a.t2<b.t2;
}
inline int read(){
    int a=0;
    char c=getchar();
    while(c>57||c<48) c=getchar();
    while(47<c&&c<58){
        a=a*10+c-48;
        c=getchar();
    }
    return a;
}//快读
void build(int nod,int l,int r){
    f[nod]=INF;
    if(l==r)return;
    build(Ls,l,mid);
    build(Rs,mid+1,r);
}//建树
LL ask(int nod,int l,int r,int b,int e){
    if(l>e||r<b)return INF;
    if((b<=l&&r<=e)||l==r) return f[nod];
    return min(ask(Ls,l,mid,b,e),ask(Rs,mid+1,r,b,e));
}//最小值
void pushup(int nod,int l,int r,int loc){
    if(l>loc||r<loc) return;
    if(l==r) {f[nod]=ans[loc];return;}
    pushup(Ls,l,mid,loc);
    pushup(Rs,mid+1,r,loc);
    f[nod]=min(f[Ls],f[Rs]);
}//修改
int main(){
    n=read();b=read();e=read();
    for(int i=1;i<=n;++i){
        w[i].t1=read();
        w[i].t2=read();
        w[i].cost=read();
    }
    build(1,b,e);
    sort(w+1,w+1+n,cmp);//按t2排序，更新完前面再更新后面
    for(int i=b;i<=e;++i)ans[i]=INF;
    for(int i=1;i<=n;++i){
        int temp=ans[w[i].t2];
        ans[w[i].t2]=min(ans[w[i].t2],((w[i].t1>b)?ask(1,b,e,w[i].t1-1,w[i].t2):0)+(LL)w[i].cost);//这里要注意，当t1为b时要特判
        if(temp!=ans[w[i].t2])pushup(1,b,e,w[i].t2);
    }
    ans[e]!=INF?printf("%lld",ans[e]):puts("-1");
    return 0;
}