DP+线段树P4644【清理牛棚】

· · 题解

前备知识：线段树（单点修改区间查询）

不会的童鞋可以去练习一下:

P3372 【模板】线段树 1

设f[x]为清理[L,x]需要花费的最小代价。 把所有的奶牛的r进行从小到大的排序，按顺序扫描这些奶牛

则f[ri]=min(f[ri],min(f[x])+ci)其中ai-1<=x<bi

初始值f[L-1]=0,其余为inf

考虑优化：min(f[x])是一个区间的最小值，f数组还需要修改，很容易想到线段树，由于本题的线段坐标比较小，直接在[L-1,R]上建树。

小提示：
  1. 当左右端点超出[L,R]边界时可以放缩到边界， 
    a[i].l=max(a[i].l,L);
a[i].r=min(a[i].r,R);
  2. 当L=0时，上述讲的f[L-1]会炸数组。只需在读入时将l,r都加一即可 
    L++;R++;
a[i].l++;a[i].r++;

    少废话,直接上代码

#include<bits/stdc++.h>
#define INF 0x7fffffff/2
using namespace std;
const int A=100005;
struct note{
    int l,r,s;
}tree[A*4],a[A];//为了方便，两个数组一起定义
int n,L,R,f[A];
bool cmp(note aa,note bb){//按照右端点排序
    return aa.r<bb.r;
}
void updata(int x){//更新操作
    tree[x].s=min(tree[2*x].s,tree[2*x+1].s);
}
void build(int x,int l,int r){//建立线段树
//  cout<<x<<" "<<l<<" "<<r<<"\n";
    tree[x].l=l;
    tree[x].r=r;
    tree[x].s=INF;
    if(l==r)return;
    int mid=(l+r)/2;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
}
void revise(int x,int k,int p){//单点修改
//  cout<<tree[x].l<<" "<<k<<" "<<tree[x].r<<"\n";
    if(k<tree[x].l||k>tree[x].r)return;
    if(tree[x].l==k&&tree[x].r==k){tree[x].s=p;return;}
    int mid=(tree[x].l+tree[x].r)/2;
    if(k<=mid)revise(2*x,k,p);
    else revise(2*x+1,k,p);
    updata(x);
}
int ask(int x,int l,int r){//区间查询
    if(r<tree[x].l||tree[x].r<l)return INF;
    if(l<=tree[x].l&&tree[x].r<=r)return tree[x].s;
    return min(ask(2*x,l,r),ask(2*x+1,l,r));
}
int main(){
    scanf("%d%d%d",&n,&L,&R);L++;R++;
    for(int i=L;i<=R;i++)f[i]=INF;//初始化为极值
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].s);
        a[i].l++;a[i].r++;
        a[i].l=max(a[i].l,L);
        a[i].r=min(a[i].r,R);
    }
    build(1,L-1,R);
    revise(1,L-1,0);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
//      cout<<a[i].l<<" "<<a[i].r<<" "<<(1,a[i].l-1,a[i].r)<<" ";
        f[a[i].r]=min(f[a[i].r],ask(1,a[i].l-1,a[i].r)+a[i].s);
//      cout<<f[a[i].r]<<"\n";
        revise(1,a[i].r,f[a[i].r]);
    }
    if(f[R]==INF)puts("-1");
    else printf("%d",f[R]);
    return 0;
}

结束语（与本题无关）：如果坐标很大时可以考虑离散化哦！