poj3171（线段树区间覆盖最小代价）

题意：给n个区间及其代价值，问要覆盖[M,E]区间至少要花费多少代价；

解法：线段树维护和查询区间的最小值：

           先将所有区间的代价设置为无限大，然后[0,M-1]区间设置为0.将给的n区间按左优先排序，然后进行一趟遍历：第i个区间为[a,b]，先查询[a-1,b]区间的最小值min然后更新[a,b]的最小值为Ci+min。最后找到[E,E]区间的最小值就是要覆盖[M,E]区间的最小代价了，若大于等于无限大值则说明中间有段区间无法覆盖；

         线段树节点有两个维护量nMin和Allmin;nMin表示此区间内真正的最小值，Allmin表示的是更新此全区间并且没有下放的值(这个是线段树能做到nlogn的关键原因)；维护时候只要到达完整区间就停止，查询时候再下放Allmin值；

代码：

#include <iostream>
#include <algorithm>
#include <numeric>
#include <stdio.h>
using namespace std;
long long MY_MIN=1000000000000;
struct CNode
{
    int L,R;
    long long nMin,Allmin;
    CNode * pLeft, * pRight;
};
CNode Tree[10000000];
int N,M,E;
int nCount = 0;
void BuildTree(CNode * pRoot, int L,int R)
{
    pRoot->L = L;
    pRoot->R = R;
    pRoot->nMin = MY_MIN;
    pRoot->Allmin = MY_MIN;
    if ( L != R)
    {
        nCount ++;
        pRoot->pLeft = Tree + nCount;
        nCount ++;
        pRoot->pRight = Tree + nCount;
        BuildTree( pRoot->pLeft, L, ( L + R )/2);
        BuildTree( pRoot->pRight, (L + R) / 2 + 1,R);
    }
}

void Insertmin(CNode * pRoot, int s, int e,long long v)
{
    pRoot->nMin = min(pRoot->nMin,v);
    if( s == pRoot->L && e == pRoot->R)
    {
        pRoot->Allmin = min(pRoot->Allmin,v);
        return ;
    }
    if( e <= (pRoot->L + pRoot->R) / 2 ) Insertmin(pRoot->pLeft, s,e,v);
    else if( s >= (pRoot->L + pRoot->R) / 2 + 1) Insertmin(pRoot->pRight, s,e,v);
    else
    {
        Insertmin(pRoot->pLeft, s,(pRoot->L + pRoot->R) / 2,v);
        Insertmin(pRoot->pRight, (pRoot->L + pRoot->R) / 2+1 ,e,v);
    }
}
long long Query(CNode * pRoot, int s, int e)
{
    if( s == pRoot->L && e == pRoot->R)
    {
        return pRoot->nMin;
    }
    Insertmin(pRoot->pLeft, pRoot->L,(pRoot->L + pRoot->R) / 2,pRoot->Allmin);
    Insertmin(pRoot->pRight, (pRoot->L + pRoot->R) / 2+1 ,pRoot->R,pRoot->Allmin);
    if( e <= (pRoot->L + pRoot->R) / 2 ) return Query(pRoot->pLeft, s,e);
    else if( s >= (pRoot->L + pRoot->R) / 2 + 1) return Query(pRoot->pRight, s,e);
    else
    {
        return min(Query(pRoot->pLeft, s,(pRoot->L + pRoot->R) / 2),Query(pRoot->pRight, (pRoot->L + pRoot->R) / 2+1 ,e));
    }
}
struct point
{
    int left,right;
    int cost;
} points[10010];
bool operator<(point a,point b)
{
    if(a.left!=b.left)
    return a.left<b.left;
    return a.right<b.right;
}
int main()
{
    BuildTree(Tree,0, 100100);
    scanf("%d%d%d",&N,&M,&E);M++,E++;
    Insertmin(Tree,0,M-1,0);
    for(int i=0;i<N;i++)
    scanf("%d%d%d",&points[i].left,&points[i].right,&points[i].cost),points[i].left++,points[i].right++;
    sort(points,points+N);
    for(int i=0;i<N;i++){
       Insertmin(Tree,points[i].left,points[i].right,points[i].cost+Query(Tree,points[i].left-1,points[i].right));
    }
    long long ans=Query(Tree,E,E);
    if(ans>=MY_MIN)
        cout<<"-1\n";
    else
        cout<<ans<<endl;
    return 0;
}
/*
4 0 4
0 4 4
0 2 3
3 4 2
0 0 1
*/

poj3171（线段树区间覆盖最小代价）,布布扣,bubuko.com

poj3171（线段树区间覆盖最小代价）

原文：http://blog.csdn.net/xiefubao/article/details/23177035