HDU 3607 線段樹+離散化+DP

HDU 3607 線段樹+離散化+DP

N個連續的盒子，每個盒子有高度h和價值v，選擇任意一點進入，且從任意一點出來，進入後只能從左向右走，且每次走到的盒子高度必須更高，可以跳過低的盒子

狀態轉移方程：dp[i]=max(dp[j])+v[i], (0<=jh[j])

用線段樹優化，尋找 j

#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.hmid) 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;
}