d069: P-6-6. 方格棋盤路線
Tags : DP
Accepted rate : 18人/19人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-11-18 19:57

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:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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