题目描述
囧一个,我倒是觉得这到题目比较难啊,毕竟我不会用搜索,结果要用自己更不会的DP(其实就是一个伪DP啦 
)
首先将珠子copy一遍,就可以做到环状遍历了.因为题目是上到350的,如果用string就杯具了,最好还是用ansistring,或者用数组(不过在copy的时候还是要麻烦点啦).
然后从左往右数:
[cc lang="Pascal"]for i:=1 to 2*n do
begin
if beads[i-1]='r' then
begin
left[i,0]:=left[i-1,0]+1;
left[i,1]:=0;
end;
if beads[i-1]='b' then
begin
left[i,0]:=0;
left[i,1]:=left[i-1,1]+1;
end;
if beads[i-1]='w' then
begin
left[i,0]:=left[i-1,0]+1;
left[i,1]:=left[i-1,1]+1;
end;
end;[/cc]
然后再在最后处理下最大值就好了
ans=min(n,max(max(left[i,0],left[i,1])+max(right[i,0]+right[i,1])))
[cc lang="Pascal"]const
maxn=360;
var
left,right:array[0..maxn,0..1] of integer;{0:r,1:b}
beads:ansistring;
i,n,ans:integer;
procedure Init;
begin
fillchar(left,sizeof(left),0);
fillchar(right,sizeof(right),0);
end;
function whoMax(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;
function whoMin(a,b:integer):integer;
begin
if a>b then exit(b) else exit(a);
end;
begin
Init;
readln(n);readln(beads);
beads:=beads+beads;
left[0,0]:=0;left[0,1]:=0;
for i:=1 to 2*n do
begin
if beads[i-1]='r' then
begin
left[i,0]:=left[i-1,0]+1;
left[i,1]:=0;
end;
if beads[i-1]='b' then
begin
left[i,0]:=0;
left[i,1]:=left[i-1,1]+1;
end;
if beads[i-1]='w' then
begin
left[i,0]:=left[i-1,0]+1;
left[i,1]:=left[i-1,1]+1;
end;
end;
right[2*n,0]:=0;right[2*n,1]:=1;
for i:=2*n downto 1 do
begin
if beads[i+1]='r' then
begin
right[i,0]:=right[i+1,0]+1;
right[i,1]:=0;
end;
if beads[i+1]='b' then
begin
right[i,0]:=0;
right[i,1]:=right[i+1,1]+1;
end;
if beads[i+1]='w' then
begin
right[i,0]:=right[i+1,0]+1;
right[i,1]:=right[i+1,1]+1;
end;
end;
ans:=-maxint;
for i:=1 to 2*n do
ans:=whoMax(ans,whoMax(left[i,0],left[i,1])+whoMax(right[i,0],right[i,1]));
ans:=whoMin(ans,n);
writeln(ans);
end.[/cc]
迟点真得恶补一下搜索+动规,囧
ASCAL
