程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3607 線段樹+離散化+DP

HDU 3607 線段樹+離散化+DP

編輯:C++入門知識

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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved