【动态规划】数字三角形3

【题目描述】

数字三角形必须经过某一个点，使之走的路程和最大

【输入格式】

第1行n，表示n行 <=25
第2到n+1行为每个的权值
程序必须经过n div 2,n div 2这个点

【输出格式】

最大值

【分析】

其实也有非常多的做法。

做法一：我们找出从(1,1)到(n div 2,n div 2)的最大值，在找出从(n div 2,n div 2)到底部的最大值，加在一起也是最优解。

做法二：我们在(n div 2,n div 2)上加上一个非常大的数，然后普通的数字三角形做一下就可以了，最后把大数减掉就可以了。

【代码】

 1 const
 2   maxn=10000000;
 3 var
 4   n,i,j:longint;
 5   f,a:array[0..25,0..25]of longint;
 6 function max(n,m:longint):longint;
 7   begin
 8     if n>m then exit(n) else exit(m);
 9   end;
10 begin
11   fillchar(f,sizeof(f),0);
12   readln(n);
13   for i:=1 to n do 
14     for j:=1 to i do 
15     begin
16       read(a[i][j]);
17       f[i][j]:=a[i][j];
18     end;
19   inc(f[n div 2][n div 2],maxn);
20   for i:=n downto 1 do
21     for j:=1 to i do 
22       f[i][j]:=max(f[i+1][j],f[i+1][j+1])+f[i][j];
23   writeln(f[1][1]-maxn);
24 end.

【动态规划】数字三角形3

相关推荐