HDU 3607 线段树+DP+离散化

题意：从左往右跳箱子，每个箱子有金币数量，只能从矮处向高处跳，求最大可获得金币数，数据规模1<=n<=1e5.

显然是一个dp的问题，不难得出dp[ i ] = max(dp[j] )+val [ i ] ,j < i ; 第一眼会想到o(n^2)的算法，显然会超时，这个时候就需要用线段树维护最大值，将复杂度降低到o(nlogn)

首先离散化处理，将高度从小到大排序，并使用unique函数去重，之后每个高度就可以映射为它的下标pos，然后用线段树维护每个下标对应的最优解bestans [ pos ] ，每当向后进行新的决策时，

先找出状态转移方程中的max( dp [ j ] ) ,线段树操作是o(logn)的，然后用dp [ i ] = max( dp [ j ])+val[ i ] 更新线段树中 ( h[ i ] 对应下标pos ) bestans[ pos ] 的值

#include<bits/stdc++.h>

#define N 100050

#define debug cout<<"???"<<endl;

using namespace std;

int val[N],mx[N<<],h[N];

void pushup(int rt)

{

    mx[rt]=max(mx[rt<<],mx[rt<<|]);

}

int query(int L,int R,int l,int r,int rt)

{

    if(L>R)return ;

    if(L<=l&&r<=R)return mx[rt];

    int m=(l+r)>>;

    int ans=;

    if(L<=m)ans=max(ans,query(L,R,l,m,rt<<));

    if(R>m)ans=max(ans,query(L,R,m+,r,rt<<|));

    return ans;

}

void updata(int pos,int val,int l,int r,int rt)

{

    if(l==r){

        mx[rt]=val;

        return;

    }

    int m=(l+r)>>;

    if(pos<=m)updata(pos,val,l,m,rt<<);

    if(pos>m)updata(pos,val,m+,r,rt<<|);

    pushup(rt);

}

void init()

{

    memset(mx,, sizeof(mx));

}

int main()

{

    int n,x;

    while(cin>>n) {

        init();

        vector<int>ve;

        for (int i = ; i <= n; i++) {

            scanf("%d%d",&h[i],val+i);

            ve.emplace_back(h[i]);

        }

        int ans=;

        sort(ve.begin(),ve.end());

        unique(ve.begin(),ve.end());

        for(int i=;i<=n;i++)

        {

            int pos=int(lower_bound(ve.begin(),ve.end(),h[i])-ve.begin()+);

            int tmp=query(,pos-,,int(ve.size()),);

            updata(pos,tmp+val[i],,int(ve.size()),);

            ans=max(ans,tmp+val[i]);

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

HDU 3607 线段树+DP+离散化

最新文章

热门文章