Description
被认为天才的小头遇到麻烦了！！这天数学课老师给出了一道难题，而小头居然没能在3秒内解决，可见此题难度之大。 问题是这样的：n个整数围成一个环，老师要求选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于1。在满足这个前提下，问最多能取多少个数。
Input
第一行一个正整数n，表示有n个数 第二行n个整数，a1、a2……an 按顺时针方向围成一个环。
Output
一个正整数，即表示最多能选多少个数。 题解 需要发现一个性质。即枚举完起点把环转化成一行后，用dp[i]表示以第i个数结尾最多能选多少个数，那么在求dp[i]时只需要记录dp[1]到dp[i-1]里前3大的数就可以了（显然3个不同数中至少有一个和a[i]的绝对值不等于1）。同理，在枚举起点时也只要枚举前5个不同的数。因此该题复杂度为O(N)。 但本人笨，不会。于是在用LXF的方法做对。 用dp[i]表示以第i个数结尾最多能选多少个数。 那我们只能在dp[1]..d[i-1]的范围中找到一个最大的dp[j]，且a[j]是在 0..a[i]-2,a[i],a[i]+2..max的范围中(因为a[i]-1和a[i]+1与a[i]的差的绝对值等于1)。 可以把原队列复制一次在队尾，把数的个数变成n*2，就可以处理环的最后一个数和第一个数是否冲突。 输出时输出max(dp[i]) div 2。 可以用线段树来优化这一过程（范围找最大)。
最后，我在此吐槽一句，后面的方法是水解。因为数据太水。我的代码不能处理(3,3,3,3,6,6,6,2,2,4,4)结果是7，而我的是9。希望大家能告诉我那错了。
代码
type arr=record nm,w:longint; end; var ans,n,m:longint; t:array [0..400001] of longint; f,h:array [0..200001] of longint; a:array [0..200001] of arr; function max(o,p:longint):longint; begin if o>p then exit(o) else exit(p); end; function ins(p,x,y,l,r:longint):longint; var mid:longint; begin if (x=l) and (y=r) then exit(t[p]); mid:=(l+r) div 2; if y<=mid then exit(ins(p*2,x,y,l,mid)) else if mid+1<=x then exit(ins(p*2+1,x,y,mid+1,r)) else exit(max(ins(p*2,x,mid,l,mid),ins(p*2+1,mid+1,y,mid+1,r))); end; procedure count(x,y,l,r,sum:longint); var mid:longint; begin if l=r then begin t[x]:=max(t[x],sum); exit; end; mid:=(l+r) div 2; if y<=mid then count(x*2,y,l,mid,sum) else count(x*2+1,y,mid+1,r,sum); t[x]:=max(t[x*2],t[x*2+1]); end; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2].nm; repeat while a[i].nm<mid do inc(i); while a[j].nm>mid do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure main; var i,x,y,z:longint; begin fillchar(f,sizeof(f),0); for i:=1 to n*2 do begin if h[i]-2>0 then x:=ins(1,1,h[i]-2,1,m) else x:=0; if h[i]+2<m+1 then y:=ins(1,h[i]+2,m,1,m) else y:=0; z:=ins(1,h[i],h[i],1,m); f[i]:=max(max(x,y),z)+1; count(1,h[i],1,m,f[i]); end; ans:=0; for i:=1 to n*2 do ans:=max(f[i],ans); end; procedure init; var i:longint; begin readln(n); for i:=1 to n do begin read(h[i]); h[i+n]:=h[i]; end; for i:=1 to n<<1 do begin a[i].nm:=h[i]; a[i].w:=i; end; qsort(1,n*2); m:=1; h[a[1].w]:=m; for i:=2 to n<<1 do begin if abs(a[i].nm-a[i-1].nm)=1 then inc(m) else if a[i].nm<>a[i-1].nm then inc(m,2); h[a[i].w]:=m; end; end; begin init; main; write(ans div 2); end.