d069. P-6-6. 方格棋盤路線

Content

在一個 m*n 方格棋盤上，每個格子都有一個分數(可正可負)，現在要從左上角的格

子走到右下角，每次只能從當時位置移動到右方或下方的格子，請計算出經過路線上

的數字的最大可能總和。以下圖為例，最大的總和路線是經過 (2, -2, 5, 7, -5, 4)，總合為 11。

2 -2 3 3

-6 5 2 -8

4 7 -5 4

Input

第一行有兩個正整數 m 與 n。接下來 m 行，每行 n 個整數，代表方格由上

而下，由左而右的內容。m 與 n 皆不超過 200，矩陣內的數字絕對值皆不超過 1e4。

Output

最大總和。

Sample Input

//case 1
3 4
2 -2 3 3
-6 5 2 -8
3 7 -5 4
//case 2
2 5
1 2 3 1 -5
-2 5 -8 2 1

Sample Output

//case 1
11
//case 2
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 ：

Tags:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)

]

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