A 清理垃圾

總時(shí)間限制:1000ms 內(nèi)存限制:128 MB

問題描述

跳蚤國(guó)垃圾成山辣！
最近由于沒人收拾垃圾，垃圾堆積成山導(dǎo)致跳蚤們已經(jīng)無處可跳了！
現(xiàn)在已知跳蚤國(guó)是一個(gè)二維的平面，有一只跳蚤清潔員 qqqopop 在原點(diǎn)(0,0) 處，
將要走到 (n,m) 點(diǎn)去,由于一些奇怪的原因，每次他都只能向右跳一格或者向上跳一格，
假設(shè)他所在的位置有一個(gè)垃圾，那他就可以拿走這個(gè)垃圾并為國(guó)家貢獻(xiàn)一個(gè)愉悅值，
不同垃圾帶給國(guó)家的愉悅值是不同的。
問題來了，
跳蚤清潔員到能為國(guó)家貢獻(xiàn)多少愉悅值呢？
跳蚤國(guó)王當(dāng)然是會(huì)的，但是他要考考你……

輸入格式

第一行三個(gè)數(shù) n,m,k,
表示清潔員要走到 (n,m) 處，
整張地圖上一共有 k 個(gè)位置有垃圾，
接下來 k 行，每行三個(gè)數(shù)字 x,y,val，
表示該垃圾在 (x,y) 處，能為國(guó)家貢獻(xiàn) val 的愉悅值

輸出格式

一行一個(gè)數(shù)位最多的愉悅值

樣例輸入

8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2

樣例輸出

11

提示

數(shù)據(jù)規(guī)模與約定：
對(duì)于 30% 的數(shù)據(jù)，有 0 < n,m ≤ 1000.
對(duì)于 100% 的數(shù)據(jù)，有 0< n,m ≤ 10 5 ，保證一個(gè)地方不會(huì)有多個(gè)垃
圾，每個(gè)垃圾都在 (0,0) 到 (n,m) 的矩形范圍內(nèi)，保證答案在 int 范圍內(nèi)

實(shí)現(xiàn)代碼[部分分?jǐn)?shù)]

……

題解
DFS搜索即可，不過不能存數(shù)組，存數(shù)組時(shí)間上和空間上都要掛，用結(jié)構(gòu)體存垃圾的信息就好了。