本文主要是介绍HDU 4521 小明系列问题——小明序列 (线段树维护DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 4521
基本思路是DP。找前面数的最大值时可以用线段树来维护节省时间。
由于间隔要大于d。所以可以用一个队列来延迟更新，来保证每次询问到的都是d个之前的。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>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){queue<node>q;for(i=0;i<n;i++){scanf("%d",&a[i]);}memset(maxv,0,sizeof(maxv));for(i=0;i<n;i++){q_maxv=0;if(a[i])Query(0,a[i]-1,0,100000,1);now.maxv=q_maxv;now.num=a[i];q.push(now);if(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;
}
这篇关于HDU 4521 小明系列问题——小明序列 (线段树维护DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
