题目描述

奶牛们去 bowling（保龄球）时并不使用真正的保龄球，而是每个奶牛拿一个数字（范围在 0 到 99 之间），并排成一个类似保龄球瓶的三角形，例如：

$ \begin{matrix} & & & & 7 & & & \\ & & & 3 & & 8 & \\ & & 8 & & 1 & & 0 \\ & 2 & & 7 & & 4 & & 4 & \\ 4 & & 5 & & 2 & & 6 & & 5 \\ \end{matrix} $

然后其他奶牛从三角形的顶端出发，每次向下移动到斜对角相邻的两个奶牛之一，直到到达最底层。奶牛的得分是路径上所有数字的和，得分最高的奶牛赢得这一局。

给定一个有 N（$1 \leq N \leq 350$）行的三角形，求可能达到的最大分数。

输入格式

• 第 1 行：一个整数 N
• 第 2 行到第 N+1 行：第 i+1 行包含 i 个用空格分隔的整数，表示三角形的第 i 行

输出格式

• 第 1 行：按照规则遍历能得到的最大和

输入样例 1

5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5  

输出样例 1

30  

提示

样例解释：

          7

         *

        3   8

       *

      8   1   0

       *

    2   7   4   4

       *

  4   5   2   6   5

如上图所示，按此路径遍历奶牛可获得最高分数。

题目来源

USACO 2005 年 12 月青铜组

关键说明

• 数字范围：每个数字在 $0$ 到 $99$ 之间
• 三角形行数 N 最大为 350，需考虑动态规划的高效解法
• 路径规则：每次只能向下移动到斜对角相邻的位置（即当前位置的左下方或右下方）