环中环

Description

---

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

Input

---

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

Output

---

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

Hint

---

[样例解释]

　　 最多能选3个数 　　 既选择（1，3，5）或者（2，5，2）

[数据范围]

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

Analysis

---

类似最长不下降子序列的dp，稍改可以80分，于是我机(wei)智 (suo) 地开了O2，仍然TLE一个点不过90分到手 f[i]=max(f[j]+1)(|a[i]−a[j]|≠1)

另一种方法通过用一颗线段树，记录下标a[i]表示以a[i]为结尾的f[i]值，每次查找三个合法区间的最大值更新一下线段树，找一个最大值作为最后答案输出

Code

---

#include <stdio.h> using namespace std; struct tree { int l,r,c; }; tree t[4000010]; int a[400010]; __attribute__((optimize("O2"))) int max(int x,int y) { return x>y?x:y; } __attribute__((optimize("O2"))) void build(int f,int x,int y) { t[f]=(tree){x,y,0}; if (x==y) return; int mid=(x+y)>>1; build(f+f,x,mid); build(f+f+1,mid+1,y); } __attribute__((optimize("O2"))) void insert(int f,int x,int y,int c) { int mid=(t[f].r+t[f].l)>>1; t[f].c=max(t[f].c,c); if ((x==t[f].l)&&(y==t[f].r)) t[f].c=max(t[f].c,c); else if (y<=mid) insert(f+f,x,y,c); else if (x>=mid+1) insert(f+f+1,x,y,c); else { insert(f+f,x,mid,c); insert(f+f+1,mid+1,y,c); } } __attribute__((optimize("O2"))) int find(int f,int x,int y) { if (y<x) return 0; if (t[f].l==x&&t[f].r==y) return t[f].c; int mid=(t[f].l+t[f].r)>>1; if (y<=mid) return find(f+f,x,y); else if (x>=mid+1) return find(f+f+1,x,y); else return max(find(f+f,x,mid),find(f+f+1,mid+1,y)); } __attribute__((optimize("O2"))) int main() { int n,max_num=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); max_num=max(max_num,a[i]); a[i+n]=a[i]; } build(1,0,max_num); int x=0,ans,tmp; for (int i=1;i<=n*2-1;i++) { ans=0; tmp=find(1,0,a[i]-2); ans=max(tmp,ans); tmp=find(1,a[i],a[i]); ans=max(tmp,ans); tmp=find(1,a[i]+2,max_num); ans=max(tmp,ans); ans++; insert(1,a[i],a[i],ans); x=max(ans,x); } printf("%d\n",(x+1)>>1); return 0; } #include <stdio.h> #include <cmath> using namespace std; int f[1001001],a[1001001],t[1001001]; __attribute__((optimize("O2"))) int main() { int n,ans=0; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[1]=1; t[1]=1; for (int i=2;i<=n;i++) { int max=0; for (int j=i-1;j>=1;j--) if (f[j]>f[max]&&(abs(a[j]-a[i])!=1)) max=j; t[i]=i; if (max) t[i]=t[max]; f[i]=f[max]+1; if (f[i]>ans) if (abs(a[i]-a[t[i]])!=1) ans=f[i]; else ans=f[i]-1; } printf("%d\n",ans); return 0; }