描述

数字三角形

要求走到最后mod 100最大

输入格式

第1行n，表示n行 <=25

第2到n+1行为每个的权值

输出格式

mod 100最大值

测试样例1

输入

2

1

99 98

输出

99

题目分析：

    数字三角形是一道经典的题目，因此它有许多强化版本。我做了2——4。虽然他们大同小异，我还是发上来，以便大家扩充思路。（其实我的代码p,c交互是有原因的，因为我暑假开始转C，同时才开始刷题，所以有的题是P，有的题是C）

    那么回到正题。这道题我用了一个三维的布尔数组f[i][j][k]。利用HASH的思想，直接保存mod 100后是否能到。状态转移方程就很好写了。最后枚举k就行了。

源代码：

var i,j,k,n:longint;  f:array[0..26,0..26,0..99]of boolean;  a:array[0..26,0..26]of longint;begin  fillchar(f,sizeof(f),false);  readln(n);  for i:=1 to n do    for j:=1 to i do read(a[i,j]);  f[1,1,a[1,1]mod 100]:=true;  for i:=2 to n do    for j:=1 to i do      for k:=0 to 99 do        begin          if f[i-1,j,k] then f[i,j,(k+a[i,j])mod 100]:=true;          if f[i-1,j-1,k] then f[i,j,(k+a[i,j])mod 100]:=true;        end;  for i:=99 downto 0 do    for j:=1 to n do      if f[n,j,i] then        begin          writeln(i);          exit;        end;end.