记录编号	1333	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.006 s
提交时间	2008-09-01 21:10:41	内存使用	0.23 MiB

{Made by Cui Hao}
program shuta;

var n,i,j:longint;                                  
     {n:读取数塔层数; i,j:循环控制变量;}
    max,st,nex:array[1..100,1..100]of longint;      
     {数组[max:纪录从该位置开始最大数字和; st:记录数塔上该位置的数; nex:记录该位置开始和最大数字序列中下一个数字横排位置;}
    f1:text;
     {f1:输入输出变量;}

begin
 assign(f1,'shuta.in');
 reset(f1);

 readln(f1,n);

 for i:=1 to n do
  for j:=1 to i do
  begin
   read(f1,st[i,j]);
   max[i,j]:=st[i,j];
    {max赋初值为当前该位置上的数}
  end;

 close(f1);
  {读入数塔}

 for i:=n-1 downto 1 do
  for j:=1 to i do
   if max[i+1,j]>=max[i+1,j+1] then
   begin
    max[i,j]:=max[i,j]+max[i+1,j];
    nex[i,j]:=j;
     {如果下一行左边的位置开始最大数字和较大，该位置开始最大数字和max加上前者，并纪录下一个数字位置}
    end else
    begin
     max[i,j]:=max[i,j]+max[i+1,j+1];
     nex[i,j]:=j+1;
      {如果下一行右边的位置开始最大数字和较大，该位置开始最大数字和max加上前者，并纪录下一个数字位置}
    end;
  {从尾到头计算该位置开始最大数字和}

 assign(f1,'shuta.out');
 rewrite(f1);

 writeln(f1,max[1,1]);

 j:=nex[1,1];
 write(f1,st[1,1],' ');
 for i:=2 to n do
 begin
  write(f1,st[i,j],' ');
  j:=nex[i,j];
 end;
  {输出路径，每次把下一个数字位置赋给j，每次输出该行j位置的数}

 close(f1);
  {输出}
end.