789 . 勇者修煉
TopCoder
Description
輸入為 $n\times m$ 大小的的陣列，每一格是一個介於 $-100$ 與 $100$ 之間的整數，表示經過這格可以累積的經驗值。
你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。
過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。
請你算出最多可以獲得的經驗值總和（可能是負數）。
Input Format
第一行有兩個正整數 $n,m(1\leq n\leq 50,1\leq m\leq 10000)$。
接下來 $n$ 行，每行包含 $m$ 個整數。第 $i$ 行的第 $j$ 個數字表示在 $(i,j)$ 位置可以得到的經驗值 $v_{ij} (-100\le v_{ij}\le 100)$。
配分：
- $20\%$：$n=1,1\leq m\leq 100$
- $30\%$：$1\leq m\leq 100$
- $50\%$：無額外限制
Output Format
輸出可以獲得的最多經驗值總和。
Sample Input 1
1 5
2 1 4 -7 4
2 1 4 -7 4
Sample Output 1
7
Hints
Problem Source
APCS 歷屆
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~5 | $1\le n\le 100,m=1$ | 20 |
| 3 | 0~15 | $1\le n\le 100$ | 30 |
| 4 | 0~25 | 無額外限制 | 50 |