[DP][线段树]环中环

本文主要是介绍[DP][线段树]环中环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

Input

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

Output

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

Sample Input

5
1 2 3 5 2

Sample Output

3

Data Constraint

Hint

【样例解释】
　　 最多能选3个数
　　 既选择（1，3，5）或者（2，5，2）
【数据范围】
　　 30%的数据，n≤10
　　 50%的数据，n≤100
　　 70%的数据，n≤1000
　　 100%的数据，n≤100000，ai≤1100000

分析

这题首先我们考虑设DP
设fi为选择第i个数时，最多能选得数
那么易得fi=max{fj(aj±1≠ai)
我们可以考虑使用一棵二分树来维护f，这样我们只需要寻找0~ai-2 ai+2~1100000 和ai~ai（即找自己）即可
同时因为这题是环，所以哪个作为起点都行，那么我们把数列翻倍，易知答案除以2就是原环的答案（相当于double了一个环）

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (i=a;i<=b;i++)
#define q(x) tree[x]
using namespace std;
int n,i;
int a[200001];
int f[200001],tree[4400001];
void change(int p,int l,int r,int d)
{if (l==r){q(p)=f[i];return;}int mid=(l+r)/2;if (d<=mid) change(p*2,l,mid,d);else change(p*2+1,mid+1,r,d);q(p)=max(q(p*2),q(p*2+1));
}
int ask(int p,int x,int y,int l,int r)
{if (r<0||l>1100000) return 0;int val=0;if (x==l&&y==r)return q(p);int mid=(x+y)/2;if (r<=mid) val=ask(p*2,x,mid,l,r);elseif (mid<l) val=ask(p*2+1,mid+1,y,l,r);else{val=ask(p*2,x,mid,l,mid);val=max(val,ask(p*2+1,mid+1,y,mid+1,r));}return val;
}
int main()
{scanf("%d",&n);rep(i,1,n){scanf("%d",&a[i]);a[i+n]=a[i];}rep(i,1,2*n){f[i]=max(ask(1,0,1100000,a[i]+2,1100000),max(ask(1,0,1100000,0,a[i]-2),ask(1,0,1100000,a[i],a[i])))+1;change(1,0,1100000,a[i]);}printf("%d",q(1)/2);
}

这篇关于[DP][线段树]环中环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---