a551:
C. The Greedy Mouse
內容
有一隻老鼠叫做 Dymose
有一天他被放在一個 $N\times M$ 的空間裡
左上角為 $(1, 1)$ ，右下角為 $(N, M)$
每一格裡都有著熱量不同但體積相同的起司
老鼠洞在最左邊一整行，所以他一定是從最左邊出發
且格子可以重複走 (但起司只有一個)
如果要跨列走，則必須回到老鼠洞才可換行 (不然會觸發陷阱)
Dymose 想要吃到愈多熱量愈好
但礙於胃的空間有限，所以他只能吃 $C$ 個起司
由於 Dymose 很貪吃
所以只要是他經過的起司都會被他吃掉
在他走格子的同時，會有陷阱的出現
但只要 Dymose 在同一橫列裡，不要跨格走就一定不會觸發陷阱 (如下圖)
請你幫 Dymose 計算一下他能安全吃到的最大熱量
輸入說明
第一行有一正整數 $T$ 代表有 $T$ 筆測資
每筆測資的第一行為 $NMC$
接下來有 $N$ 行
每行有 $M$ 個正整數代表起司的熱量
輸出說明
輸出 Dymose 能安全吃到的最大熱量
範例輸入
1 5 3 6 17 10 2 24 27 28 25 3 21 25 19 5 18 8 4
範例輸出
148
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 0.5s , <1M
公開 測資點#1 (80%): 0.5s , <1M
公開 測資點#0 (20%): 0.5s , <1M
公開 測資點#1 (80%): 0.5s , <1M
提示 ：
$T\leq 100$
$C\leq N\times M$
$#00$ $N, M\leq 10$
$#01$ $N, M\leq 50$
保證答案在 $int$ 範圍內
出處:
DDJ Regular ContestRound#2
[管理者：
revival0728
(revcoding/10th 進階助教)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||