f314. 3. 勇者修煉 - 高中生程式解題系統

內容

輸入為 $m \times n$ 大小的的陣列，每一格是一個介於 -100 與 100 之間的整數，表示經過這格可以累積的經驗值。
你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。
過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。
請你算出最多可以獲得的經驗值總和(可能是負數)。

輸入說明

第一行有兩個正整數 $m, n (1 \leq m \leq 50, 1 \leq n \leq 10000)$

接下來 $m$ 行，每行包含 $n$ 個整數。第 $i$ 行的第 $j$ 個數字表示在 $(i, j)$ 位置可以得到的經驗值。

配分

20%: $n \leq 100, m = 1$
30%: $n \leq 100$
50%: $n \leq 10000$

輸出說明

輸出可以獲得的最多經驗值總和。

範例輸入 #1

1 5
2 1 4 -7 4

範例輸出 #1

測資資訊：

記憶體限制： 250 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

APCS DP

出處:

2020年10月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
31630	dfd8282@gmai ... (fishhh)	f314	解題報告	1503	2022-08-11 19:12
27610	alan8656 (阿伯)	f314	C++解題影片	1790	2021-10-18 21:10
41117	toseanlin@gm ... (Dr. SeanXD)	f314	C++詳解－左右前綴和	396	2024-07-05 11:13
39484	a302854888@g ... (小麥)	f314	Top-Down DP	583	2024-02-26 22:04
39277	qerpzzea@gma ... (賽希爾 cecill(陳宥穎))	f314	__dp	534	2024-01-31 15:10