程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4521 小明系列問題——小明序列 (線段樹維護DP)

HDU 4521 小明系列問題——小明序列 (線段樹維護DP)

編輯：C++入門知識

HDU 4521 小明系列問題——小明序列 (線段樹維護DP)

題目地址：HDU 4521

基本思路是DP。找前面數的最大值時可以用線段樹來維護節省時間。

由於間隔要大於d。所以可以用一個隊列來延遲更新，來保證每次詢問到的都是d個之前的。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define LL __int64
const int INF=0x3f3f3f3f;
struct node
{
    int maxv, num;
};
int maxv[400000], a[1100000];
int q_maxv;
void PushUp(int rt)
{
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
void Update(int p, int x, int l, int r, int rt)
{
    if(l==r)
    {
        maxv[rt]=p;
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) Update(p,x,lson);
    else Update(p,x,rson);
    PushUp(rt);
}
void Query(int ll, int rr, int l, int r, int rt)
{
    if(ll<=l&&rr>=r)
    {
        q_maxv=max(q_maxv,maxv[rt]);
        return ;
    }
    int mid=l+r>>1;
    if(ll<=mid) Query(ll, rr, lson);
    if(rr>mid) Query(ll,rr,rson);
}
int main()
{
    int n, d, i, j, top;
    node tmp, now;
    while(scanf("%d%d",&n,&d)!=EOF)
    {
        queueq;
        for(i=0;i=d)
            {
                tmp=q.front();
                q.pop();
                Update(tmp.maxv+1,tmp.num,0,100000,1);
            }
        }
        while(!q.empty())
        {
            tmp=q.front();
            q.pop();
            Update(tmp.maxv+1,tmp.num,0,100000,1);
        }
        printf("%d\n",maxv[1]);
    }
    return 0;
}