789 . 勇者修煉

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

25.0% (7/28)

Tags

apcsc apcsc-dp

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 4
1 1000 524288 65536 2 3 4
2 1000 524288 65536 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 3 4
7 1000 524288 65536 3 4
8 1000 524288 65536 3 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
Submit
Back to Top