复件 qqq.cpp

石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆

var
 n:integer;
 a:array[1..100] of longint;
 s:array[1..100,1..100] of longint;
 t:array[0..100,0..100] of longint;
 i,j,k,temp,max,min:longint;
begin
  assign(input,'shizi.in');
  reset(input);
  readln(n);
  fillchar(t,sizeof(t),0);      {计算和数组}
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
    for j:=1 to n do
      for k:=i to i+j-1 do
        begin
          if k>n then temp:=k mod n else temp:=k;
          t[i,j]:=t[i,j]+a[temp];
        end;
{动态规划求最大得分}
  fillchar(s,sizeof(s),0);
  for j:=2 to n do
    for i:=1 to n do
      for k:=1 to j-1 do
        begin
          if i+k>n then temp:=(i+k) mod n else temp:=i+k;  {处理环形问题}
          max:=s[i,k]+s[i+k,j-k]+t[i,j];
          if s[i,j]<max then s[i,j]:=max;
        end;
  max:=0;        {在最后的阶段状态中找最大得分}
  for i:=1 to n do
    if max<s[i,j] then max:=s[i,j];

{动态规划求最小得分}
  fillchar(s,sizeof(s),0);
  for j:=2 to n do
    for i:=1 to n do
      begin
        min:=maxlongint;
        for k:=1 to j-1 do
          begin
            if i+k>n then temp:=(i+k) mod n else temp:=i+k;  {处理环形问题}
            s[i,j]:=s[i,k]+s[temp,j-k]+t[i,j];
            if min>s[i,j] then min:=s[i,j];
          end;
        s[i,j]:=min;
      end;
  min:=maxlongint;  {在最后的阶段状态中找最小得分}
  for i:=1 to n do
    if min>s[i,j] then min:=s[i,j];

  writeln(max);
  writeln(min);
end.