记录编号	1327	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	Oo湼鞶oO	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-09-01 21:00:31	内存使用	0.00 MiB

{*******************************************}
{* Program Name: Shuta                     *}
{* Input File: shuta.in                    *}
{* Output File: shuta.out                  *}
{* Date: 2008.7.24                         *}
{* Programmer: Peng Bo                     *}
{*******************************************}
program shuta;
type
  jl=record                                    {用来存放数塔中的每一个节点中的数据}
    y,z:longint;                               {y,数塔节点中自身的数;z,数塔从头到当前节点的最小路经值}
    x:byte;                                    {数塔到当前节点最小路径的上一个节点的位置}
    end;
  sz=array[1..80,1..80]of jl;                  {存放数塔}
var
  s:sz;                                        {存放数塔}
  n:byte;                                      {数塔的层数}
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure input;                               {读入过程}
var
  j,k:byte;                                    {循环控制变量}
  f:text;                                      {文件变量}
begin
  assign(f,'shuta.in');                        {定义文件}
  reset(f);                                    {打开文件为读取}
  readln(f,n);
  for j:=1 to n do
    for k:=1 to j do
      read(f,s[j,k].y);                        {读取数塔中的数}
  close(f);                                    {关闭文件}

  for j:=1 to n do
    s[n,j].z:=s[n,j].y;                        {初始化数塔底层数据}
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure output;                              {输出过程}
var
  f:text;                                      {文件变量}
  t,i:byte;                                    {t,存放下一个需要数出的值的位置,i,循环控制变量}
begin
  t:=1;                                        {初始化t}
  assign(f,'shuta.out');                       {定义文件}
  rewrite(f);                                  {打开文件为写入}
  writeln(f,s[1,1].z);                         {输出所选路径的值}
  write(f,s[1,1].y,' ');                       {输出路径的开头}
  for i:=1 to (n-1) do
  begin
    write(f,s[i+1,s[i,t].x].y,' ');            {输出路径}
    t:=s[i,t].x;                               {将t赋值为下一个需要数出的数的路径}
  end;
  close(f);                                    {关闭文件}
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure main;                                {主要过程,计算最优路径}
var
  j,k:byte;                                    {循环控制变量}
begin
  for j:=(n-1) downto 1 do                     {自下而上处理数塔}
    for k:= 1 to j do
      if s[j+1,k].z>s[j+1,k+1].z               {寻找最优路径}
      then
      begin
        s[j,k].z:=s[j,k].y+s[j+1,k].z;         {计算到当前节点的最优路径和}
        s[j,k].x:=k;                           {纪录到当前节点最小路径的上一个节点的位置}
      end
      else
      begin
        s[j,k].z:=s[j,k].y+s[j+1,k+1].z;       {计算到当前节点的最优路径和}
        s[j,k].x:=k+1;                         {纪录到当前节点最小路径的上一个节点的位置}
      end;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  input;                                       {读入}
  main;                                        {计算}
  output;                                      {输出}
end.