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

题目描述：

　被认为天才的小头遇到麻烦了！！这天数学课老师给出了一道难题，而小头居然没能在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 
}