1268 . 得分高手 (Master)
TopCoder
Description
一個數字棋盤遊戲，一開始可在棋盤中任選一格為起點，並規定下一步只能選擇起點的右方或下方格子；選擇其中一個方向後，同樣只能自該選擇的格子選擇往右方或是下方的格子推進，依此類推繼續走下去，不能再回頭。每一個格子都有分數，選擇該格子就能取得上面的分數，但是分數有正得分也有負得分（扣分）。玩家可在任意時候決定不再繼續走，或是依規則走完所有能走的格子。以底下3 x 4的棋盤為例，若選擇以第 2 列第1行為起點，依序通過 3 → -1 → 8 → 6，可得此棋盤最高可得分數 16。
| -8 | 0 | 4 | -4 |
| 3 | -1 | -9 | 3 |
| -2 | 8 | 6 | -1 |
給定棋盤上每一格的分數，請寫一個程式來找出最高可得分數。
Input Format
第一列是兩個整數 m, n，代表棋盤維度大小（m 列 n 行），3 ≤ m, n ≤ 3,000（棋盤實際大小請參照評分說明）。接下來是依照棋盤維度，共有 m 列，每一列有n個整數，代表每一格的得分score，-9 ≤ score ≤ 9，且至少有一個 score > 0。
Output Format
輸出一個整數，該整數為你的程式所找的最大得分。
Sample Input 1
3 2 5
9 -2 6
4 -8 3
Sample Output 1
Sample Input 2
5 -8 5 2 4
1 1 -9 1 -2
2 -9 3 -3 9
Sample Output 2
Hints
輸入範例1的走法為3→2→5→6→3或3→9→-2→6→3；
輸入範例2的走法為5→2→4→-2→9
本題共有五組測試資料。
第一組測試資料3 ≤ m, n ≤ 5，0 ≤ score ≤ 9 ，共20 分；
第二組測試資料3 ≤ m, n ≤ 5，-9 ≤ score ≤ 9 ，共20 分；
第三組測試資料3 ≤ m, n ≤ 100，0 ≤ score ≤ 9 ，共20 分；
第四組測試資料3 ≤ m, n ≤ 100，-9 ≤ score ≤ 9 ，共20 分；
第五組測試資料m, n =3,000，-9 ≤ score ≤ 9 ，共20 分。
Problem Source
臺北市103 學年度高級中學資訊學科能力競賽程式設計試題第二題
Set by Paupière
若測資有誤請儘快聯絡管管(?
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 20 |
| 2 | 5~9 | 20 |
| 3 | 10~14 | 20 |
| 4 | 15~19 | 20 |
| 5 | 20~24 | 20 |