Description
被认为天才的小头遇到麻烦了！！这天数学课老师给出了一道难题，而小头居然没能在3秒内解决，可见此题难度之大。 问题是这样的：n个整数围成一个环，老师要求选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于1。在满足这个前提下，问最多能取多少个数。
第一行一个正整数n，表示有n个数 第二行n个整数，a1、a2……an 按顺时针方向围成一个环。
Output
一个正整数，即表示最多能选多少个数。
分析
用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)。
输出时输出max(dp[i])。
可以用线段树来优化这一过程（范围找最大)。
代码
const
maxn=
300000;
type
pnode=^tnode;
tnode=
record
lc,rc:pnode;
c,xia:longint;
end;
var
f,s:
array[
0..maxn]
of longint;
data:
array[
0..maxn]
of longint;
ans:longint;
n,m:longint;
d:longint;
t:pnode;
procedure neww(var t:pnode);
begin
if t=
nil then
begin
new(t);
t^.c:=
0;
t^.lc:=
nil;
t^.rc:=
nil;
end;
end;
procedure insert(var t:pnode; l,r,x,y,co,xi:longint);
var
i,j,k:longint;
mid:longint;
begin
with t^
do
begin
if c<co
then
begin
c:=co;
xia:=xi;
end;
mid:=(l+r)
div 2;
if (l=x)
and (r=y)
then
exit;
if (l<=x)
and (mid>=y)
then
begin
neww(lc);
insert(lc,l,mid,x,y,co,xi);
exit;
end;
if (mid<x)
and (r>=y)
then
begin
neww(rc);
insert(rc,mid+
1,r,x,y,co,xi);
exit;
end;
neww(lc);
neww(rc);
insert(lc,l,mid,x,mid,co,xi);
insert(rc,mid+
1,r,mid+
1,y,co,xi);
end;
end;
function find(t:pnode;l,r,x,y:longint; var x1:longint):longint;
var
mid:longint;
i,j,k:longint;
begin
if t=
nil then exit(
0);
if l>r
then exit(
0);
with t^
do
begin
mid:=(l+r)
div 2;
if (l=x)
and (r=y)
then
begin
find:=c;
x1:=xia;
exit;
end;
i:=
0;
j:=
0;
if (l<=x)
and (mid>=y)
then
begin
find:=find(lc,l,mid,x,y,x1);
exit;
end;
if (mid<x)
and (r>=y)
then
begin
find:=find(rc,mid+
1,r,x,y,x1);
exit;
end;
i:=find(lc,l,mid,x,mid,x1);
k:=
0;
j:=find(rc,mid+
1,r,mid+
1,y,k);
if i>j
then
find:=i
else
begin
find:=j;
x1:=k;
end;
end;
end;
procedure init;
var
i:longint;
begin
readln(n);
m:=
0;
for i:=
1 to n
do
begin
read(data[i]);
data[i+n]:=data[i];
if data[i]>m
then m:=data[i];
end;
end;
function max(x,y:longint):longint;
begin
if x>y
then exit(x)
else exit(y);
end;
procedure main;
var
i,j,k,l:longint;
x,y,z:longint;
ans:longint;
begin
neww(t);
insert(t,
1,m,data[
1],data[
1],
1,
1);
f[
1]:=
1;
s[
1]:=
1;
for i:=
2 to n
do
begin
x:=
0; y:=
0; z:=
0;
j:=find(t,
1,m,
1,data[i]-
2,x);
k:=find(t,
1,m,data[i]+
2,m,y);
l:=find(t,
1,m,data[i],data[i],z);
f[i]:=max(j,k);
f[i]:=max(f[i],l);
if f[i]=j
then s[i]:=x
else if f[i]=k
then s[i]:=y
else s[i]:=z;
if f[i]=
0 then s[i]:=i;
f[i]:=f[i]+
1;
insert(t,
1,m,data[i],data[i],f[i],s[i]);
end;
ans:=
0;
for i:=
1 to n
do
if (ans<f[i])
and (abs(data[s[i]]-data[i])<>
1)
then ans:=f[i];
write(ans);
end;
begin
init;
main;
end.
转载请注明原文地址: https://ju.6miu.com/read-1311154.html
