环中环 {动态规划线段树}

题目描述：

　被认为天才的小头遇到麻烦了！！这天数学课老师给出了一道难题，而小头居然没能在3秒内解决，可见此题难度之大。 　问题是这样的：n个整数围成一个环，老师要求选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于1。在满足这个前提下，问最多能取多少个数。

输入:

第一行一个正整数n，表示有n个数 第二行n个整数，a1、a2……an 按顺时针方向围成一个环。 5 1 2 3 5 2

输出：

一个正整数，即表示最多能选多少个数。 3

样例解释：

【样例解释】 　　 最多能选3个数 　　 既选择（1，3，5）或者（2，5，2）

数据规模：

【数据范围】 　　 30%的数据，n≤10 　　 50%的数据，n≤100 　　 70%的数据，n≤1000 　　 100%的数据，n≤100000，ai≤1100000

---

分析：

很明显要用dp。设f[i]表示取第i个数时的最多选的个数，枚举起点将环变成序列后dp,如图： 时间复杂度 o(n3) 。方程： f[i]=f[j]+1(1≤j≤i−1,abs(a[j]−a[i])≠1) 会时超，那怎么搞呢？ 我们发现a[i]只有1100000，那么我们可以用线段树来维护数值为a[i]时f[i]的最大值。时间复杂度变成 o(n2∗log(n)) 少了很多，但还是会时超。 貌似处理环还可以把序列copy一遍吧，又省掉了寻找起点的时间，那么时间复杂度就变成了 o(n∗log(n)) 。

---

CODE(仅供参考，不要copy标):

#include<cstdio> #include<cstring> using namespace std; int n,a[200001],f[200001],tr[5000000],zl; int max(int a, int b) { if (a>b) return(a); else return(b); } void find(int z,int x,int y,int l,int r) { if((x==l)&&(y==r)) zl=max(zl,tr[z]); else { int mid=(x+y)/2; if(r<=mid) find(z*2,x,mid,l,r); else { if(l>mid) find(z*2+1,mid+1,y,l,r); else { find(z*2,x,mid,l,mid); find(z*2+1,mid+1,y,mid+1,r); } } } } int findx(int x,int y) { zl=0; if (x>=0 && y>=0) find(1,0,1100000,x,y); else return(0); return(zl); } void change(int z,int x,int y,int l) { if(x==y) tr[z]=zl; else { int mid=(x+y)/2; if(l<=mid) change(z*2,x,mid,l); else change(z*2+1,mid+1,y,l); tr[z]=max(tr[z*2],tr[z*2+1]); } } int main() { scanf("%d",&n); int i,j,k; for (i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } memset(tr,0,sizeof(tr)); for (i=1;i<=2*n;i++) { f[i]=max(findx(a[i]+2,1100000),max(findx(0,a[i]-2),findx(a[i],a[i]))); zl=f[i]+1; f[i]+=1; change(1,0,1100000,a[i]); } printf("%d",tr[1]/2); return 0 }