题目描述
If the difference between any two adjancent elements in a sequence is not more than K, then we call this sequence is a K-diff sequence. A subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without changing the order. For example, "1 3 4 6" is a 2-diff subsequence of "1 2 3 4 5 6 7". Now give you K and a sequence whose length is N, try to find out the maximum length of the K-diff subsequence of the original sequence.
输入
The first line contains a integer T, which means there are T test cases. For each test case: The first line contains two integers: N(0 < N < 102400), K(0 <= K < 100000). The second line contains n positive integers: the orginal sequence.
输出
For each test case: Output only one line with the maximum length of the K-diff subsequence.
样例输入
2 5 2 1 3 2 2 3 5 2 1 3 4 7 2
样例输出
5 4
提示" n positive integers " 0< X <2^31
这个题很容易想到一个dp方程
dp[i]=max{dp[j]+1 | j<i, |a[j]-a[i]|<=k};
是的就是这个方程了，可是复杂度为o（n^2），这也太大了吧！但是我们在考虑一下这个方程，有一个最大值，想到线段树了吧！我们只需要维护一个区间为[a[i]-k，a[i]+k]的最大值，不就可以了吗，这个就可以了吗？不是的，看看数据吧！2^31，有那么大的数组吗？有那么大的空间吗？没有，可是有在看看n，只是10^5；这样的数组是可以开出来的，怎么开，当然是把数据离散化了，这是我的第三道再线段树上离散化求解的题目了，加油！！！
#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; const int maxn=200000; struct node { int left,right,nowmax; }tree[maxn*4]; int a[maxn],b[maxn],c[maxn]; void buildtree(int c,int x,int y) { tree[c].left=x; tree[c].right=y; if (x==y) { tree[c].nowmax=0; return; } int mid=x+(y-x)/2; buildtree(c*2,x,mid); buildtree(c*2+1,mid+1,y); tree[c].nowmax=max(tree[c*2+1].nowmax,tree[c*2].nowmax); } void insert_tree(int c,int x,int v) { if (tree[c].left==x && tree[c].right==x) { tree[c].nowmax=v; return; } int mid=tree[c].left+(tree[c].right-tree[c].left)/2; if (x<=mid) insert_tree(c*2,x,v); else insert_tree(c*2+1,x,v); tree[c].nowmax=max(tree[c*2].nowmax,tree[c*2+1].nowmax); } int get_max(int c,int x,int y) { if (tree[c].left==x && tree[c].right==y) { return tree[c].nowmax; } int mid=tree[c].left+(tree[c].right-tree[c].left)/2; if (y<=mid) return get_max(c*2,x,y); else if (x>mid) return get_max(c*2+1,x,y); else { return max(get_max(c*2,x,mid),get_max(c*2+1,mid+1,y)); } } int find(int x,int y,int v) { while (x<y) { int m=x+(y-x)/2; if (a[m]>=v) y=m; else x=m+1; } return x; } int unique(int n) { int k=1; sort(b+1,b+n+1); a[1]=b[1]; for (int i=2;i<=n;i++) if (b[i]!=b[i-1]) a[++k]=b[i]; return k; } int main() { int N,K,T,ans; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&K); for (int i=1;i<=N;i++) {scanf("%d",&b[i]);c[i]=b[i];} int nown=unique(N); buildtree(1,1,nown); ans=0; for (int i=1;i<=N;i++) { int x=find(1,nown,c[i]-K); int y=find(1,nown,c[i]+K); if (a[y]>c[i]+K) y--; int temp=get_max(1,x,y)+1; ans=max(ans,temp); int id=find(1,nown,c[i]); insert_tree(1,id,temp); } printf("%d ",ans); } return 0; }
作者 chensunrise