New TIOJ 新 TIOJ 已上線！舊 submission 已全數完成 rejudge，詳見公告。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
1288 . D. [IOI 1994] 三角旅行
TopCoder
Tags
Description
7(圖一)
3 8
8 1 0
2 7 4 4
4 5 2 6 5
圖一是一個有數字構成的三角形。現在請求出從最頂端走到最底端 最大的和是多少。
- 每個點只能往左下或右下走，底層的點不能再往下走。
- 三角形的高度介於 $1$ 到 $100$ 之間。
- 三角形上的數字都介於 $0$ 到 $99$ 之間。
Input Format
第一個是數字 $n$ 代表三角形高度。
聰明的你知道接下來是怎樣的格式。
Output Format
輸出一個貌似解答的數字。
Sample Input 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output 1
30
Hints
Problem Source
原TIOJ1288 / 雄中公假社'08 入退社考。(IOI 94 DayI pA)。Problem Setter：ggm。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |