转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526
by---cxlove
题目:给出一个序列,找出一个最长的子序列,相邻的两个数的差在d以内。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3820
DP很水,线段树也水。
dp[i]表示前i个数的最长为多少,则dp[i]=max(dp[j]+1) abs(a[i]-a[j])<=d
N^2的DP很容易想到。
接下来就是如何高效地找到满足差值在d以内的最大值。
将数字进行离散化,对于一个新的数,就可以确定一个范围,然后在这个范围进行查找dp的最值+1即可。
STL里的函数确实NB。太弱了~~~
线段树每一个结点保存的是这个区间的最值,叶子结点的值便是以这个数结尾的最长数量
#include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<string> #include<queue> #define inf 1<<28 #define M 6000005 #define N 100005 #define maxn 300005 #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) #define pb(a) push_back(a) #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long #define MOD 1000000007 #define lson step<<1 #define rson step<<1|1 using namespace std; struct Node { int left,right; int mx; } L[N*4]; int dp[N],a[N],b[N]; void Bulid(int step,int l,int r) { L[step].left=l; L[step].right=r; L[step].mx=0; if(l==r) return ; int m=(l+r)>>1; Bulid(lson,l,m); Bulid(rson,m+1,r); } void Update(int step,int pos,int val) { if(L[step].left==L[step].right) { L[step].mx=val; return; } int m=(L[step].left+L[step].right)>>1; if(pos<=m) Update(lson,pos,val); else Update(rson,pos,val); L[step].mx=max(L[lson].mx,L[rson].mx); } int Query(int step,int l,int r) { if(L[step].left==l&&L[step].right==r) return L[step].mx; int m=(L[step].left+L[step].right)>>1; if(r<=m) return Query(lson,l,r); else if(l>m) return Query(rson,l,r); else return max(Query(lson,l,m),Query(rson,m+1,r)); } int main() { int n,d; while(scanf("%d%d",&n,&d)!=EOF) { for(int i=0; i<n; i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b,b+n); int m=unique(b,b+n)-b; Bulid(1,0,m-1); int ans=0; for(int i=0; i<n; i++) { int l=lower_bound(b,b+m,a[i]-d)-b; int r=upper_bound(b,b+m,a[i]+d)-b-1; int q=Query(1,l,r); ans=max(ans,q+1); Update(1,lower_bound(b,b+m,a[i])-b,q+1); } printf("%d\n",ans); } return 0; }