HDU 3607 线段树+离散化+DP

N个连续的盒子，每个盒子有高度h和价值v，选择任意一点进入，且从任意一点出来，进入后只能从左向右走，且每次走到的盒子高度必须更高，可以跳过低的盒子

状态转移方程：dp[i]=max(dp[j])+v[i], (0<=j<i && h[i]>h[j])

用线段树优化，寻找  j<i 的最大dp值，需要先对h进行离散化

#include "stdio.h"
#include "string.h"
#include "queue"
#include "algorithm"
using namespace std;

struct Mark
{
    int h,v,id;
}b[100100],mark[100100];

struct Data
{
    int l,r,v;
}data[400010];

bool cmp(Mark a,Mark b)
{
    return a.h<b.h;
}

int Max(int a,int b)
{
    if (a<b) return b;
    else return a;
}

void build(int l,int r,int k)
{
    int mid;
    data[k].l=l;
    data[k].r=r;
    data[k].v=0;
    if (l==r) return ;

    mid=(l+r)/2;

    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
}

void updata(int h,int v,int k)
{
    int mid;
    if (data[k].l==h && data[k].r==h)
    {
        data[k].v=Max(v,data[k].v);
        return;
    }
    mid=(data[k].l+data[k].r)/2;

    if (h<=mid) updata(h,v,k*2);
    else updata(h,v,k*2+1);

    data[k].v=Max(data[k*2].v,data[k*2+1].v);
}

int query(int l,int r,int k)
{
    int mid;
    if (data[k].l==l && data[k].r==r)
        return data[k].v;

    mid=(data[k].l+data[k].r)/2;

    if (r<=mid) return query(l,r,k*2);
    else
        if (l>mid) return query(l,r,k*2+1);
    else
        return Max(query(l,mid,k*2),query(mid+1,r,k*2+1));
}

int main()
{
    int i,h,temp,ans,n;
    while (scanf("%d",&n)!=EOF)
    {
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&b[i].h,&b[i].v);
            b[i].id=i;
        }
        sort(b+1,b+1+n,cmp);
        h=1;
        mark[b[1].id].h=1;
        mark[b[1].id].v=b[1].v;
        for (i=2;i<=n;i++)
        {
            if(b[i].h!=b[i-1].h) h++;
            mark[b[i].id].h=h;
            mark[b[i].id].v=b[i].v;
        }
        build(0,h,1);
        updata(mark[1].h,mark[1].v,1);
        ans=mark[1].v;
        for (i=2;i<=n;i++)
        {
            temp=query(0,mark[i].h-1,1)+mark[i].v;
            ans=Max(ans,temp);
            updata(mark[i].h,temp,1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 3607 线段树+离散化+DP

原文：http://blog.csdn.net/u011932355/article/details/44597821