线段树优化DP。。。。
| Time Limit: 5000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
There a sequence S with n integers , and A is a special subsequence that satisfies |Ai-Ai-1| <= d ( 0 <i<=|A|))
Now your task is to find the longest special subsequence of a certain sequence S
Input
There are no more than 15 cases , process till the end-of-file
The first line of each case contains two integer n and d ( 1<=n<=100000 , 0<=d<=100000000) as in the description.
The second line contains exact n integers , which consist the sequnece S .Each integer is in the range [0,100000000] .There is blank between each integer.
There is a blank line between two cases
Output
For each case , print the maximum length of special subsequence you can get.
Sample Input
5 2 1 4 3 6 5 5 0 1 2 3 4 5
Sample Output
3 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=101000;
int n,d,a[maxn],b[maxn],t,dp[maxn];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int tree[maxn<<2];
void push_up(int l,int r,int rt)
{
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
tree[rt]=0;
return ;
}
int m=(l+r)>>1;
build(lson); build(rson);
push_up(l,r,rt);
}
int query(int l,int r,int rt,int L,int R)
{
if(L<=l&&r<=R)
{
return tree[rt];
}
int m=(l+r)>>1;
int ret=-1;
if(L<=m) ret=max(ret,query(lson,L,R));
if(R>m) ret=max(ret,query(rson,L,R));
return ret;
}
void update(int l,int r,int rt,int P,int V)
{
if(l==r)
{
tree[rt]=V;
return ;
}
int m=(l+r)>>1;
if(P<=m) update(lson,P,V);
else update(rson,P,V);
push_up(l,r,rt);
}
int main()
{
while(scanf("%d%d",&n,&d)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
b[i]=a[i];
}
sort(b+1,b+n+1);
int t=unique(b+1,b+n+1)-b-1;
memset(dp,0,sizeof(dp));
dp[1]=1;
build(1,n,1);
for(int i=1;i<=n;i++)
{
int rt=lower_bound(b+1,b+t+1,a[i])-b;
int l=lower_bound(b+1,b+t+1,a[i]-d)-b;
int r=upper_bound(b+1,b+t+1,a[i]+d)-(b+1);
dp[i]=query(1,n,1,l,r)+1;
update(1,n,1,rt,dp[i]);
}
int ans=-1;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}原文：http://blog.csdn.net/u012797220/article/details/19914087