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

Description

求一个大区间由小区间的最小代价的全覆盖。

dp[i]表示到i这一位都覆盖完的最小代价。发现这个东西应当为后缀最小值，拿树状数组维护一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,e,f[101000];
struct node{int t1,t2,w;}a[11000];
inline bool cmp(const node x,const node y){return x.t1<y.t1;}
void fix(int x,int y)
{
    while(x>0) f[x]=min(f[x],y),x-=-x&x;
}
int query(int x)
{
    if(!x) return 0;
    int re=1<<30;
    while(x<=e) re=min(re,f[x]),x+=-x&x;
    return re;
}
int main()
{
    scanf("%d%d%d",&n,&m,&e); m++,e++;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i].t1,&a[i].t2,&a[i].w);
        a[i].t1++; a[i].t2++;
    }
    sort(a+1,a+n+1,cmp);
    memset(f,0x3f,sizeof(f));
    fix(m-1,0);
    for(int i=1;i<=n;i++)
    {
        int tmp=query(a[i].t1-1);
        tmp+=a[i].w;
        fix(a[i].t2,tmp);
    }
    int ans=query(e);
    if(ans==0x3f3f3f3f) puts("-1");
    else printf("%d\n",ans);
    return 0;
}