ac1061.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1061;
const
  maxl=50;
var
  child,space:array[1..maxl]of byte;
  swap:array[boolean,1..maxl]of byte;
  s:string;
  l,p,i,j:byte;
procedure findchild(x:byte);
  begin
    if s[x]='B' then begin
      dec(p);
      findchild(p);
      dec(p);
      child[x]:=p;
      findchild(p);
    end;
  end;
function min(a,b:byte):byte;
  begin
    if a<b then min:=a else min:=b;
  end;
begin
  repeat
    readln(s);l:=length(s);
    p:=l;findchild(l);

    for i:=1 to l do
      if s[i]='B' then begin
        space[i]:=127;swap[true,i]:=127;
      end
      else begin
        space[i]:=1;swap[true,i]:=0;
      end;

    j:=1;
    while space[l]=127 do begin
      inc(j);
      for i:=1 to l do begin
        swap[odd(j),i]:=swap[not odd(j),i];
        if (s[i]='B') and (space[child[i]]+space[i-1]<j*2) then begin
          if j<space[i] then space[i]:=j;
          swap[odd(j),i]:=min(swap[odd(j),i],
                              min(swap[odd(j),child[i]]+swap[not odd(j),i-1],
                                  swap[odd(j),i-1]+swap[not odd(j),child[i]]+1));
        end;
      end;
    end;
    writeln(space[l],' ',swap[odd(j),l]);
  until seekeof;
end.