e090. P-6-6. 方格棋盤路線 - 花中程式設計挑戰系統

Content

在一個 m*n 方格棋盤上，每個格子都有一個分數(可正可負)，現在要從左上角的格子走到右下角，每次只能從當時位置移動到右方或下方的格子，請計算出經過路線上的數字的最大可能總和。以下圖為例，最大的總和路線是經過(2, -2, 5, 7, -5, 4)，總合為 11。

Time limit: 1 秒

Input

第一行有兩個正整數 m 與 n。接下來 m 行，每行 n 個整數，代表方格由上而下，由左而右的內容。m 與 n 皆不超過 200，矩陣內的數字絕對值皆不超過 1e4。

Output

最大總和。

Sample Input

範例一：
3 4
2 -2 3 3
-6 5 2 -8
3 7 -5 4

範例二輸入：
2 5
1 2 3 1 -5
-2 5 -8 2 1

Sample Output

範例一：
11

範例二：
10

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

範例一說明：如題目中說明

範例二說明：先向右走三步，向下一步，再向右一步，得分 1+2+3+1+2+1=10。

Tags:

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」