n696. 01366 - Martian Mining
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-15 14:01

Content

位於休斯頓的NASA太空中心距離德克薩斯州聖安東尼奧(今年ACM總決賽的地點)不到200英里。這裡是宇航員訓練進行“七個小矮人任務”的地方,這是太空探索的下一次巨大飛躍。火星奧德賽計劃揭示了火星表面富含yeyenum和bloggium。這些礦物是某些革命性新藥的重要成分,但在地球上極為稀有。“七個小矮人任務”的目標是在火星上開採這些礦物並將它們帶回地球。

火星奧德賽探測器確定了火星表面一個富含礦物的矩形區域。該區域被劃分為n行m列的網格,其中行從東到西,列從北到南。探測器確定了每個單元格中yeyenum和bloggium的含量。宇航員將在矩形區域的西部建造yeyenum精煉廠,在北部建造bloggium精煉廠。你的任務是設計一個輸送帶系統,讓他們能夠開採到最多的礦物。

有兩種類型的輸送帶:第一種將礦物從東向西運輸,第二種將礦物從南向北運輸。在每個單元格中,你可以建造任意一種類型的輸送帶,但不能在同一單元格中建造兩種輸送帶。如果相鄰的兩個單元格有相同類型的輸送帶,它們可以連接。例如,一個單元格中開採的bloggium可以通過一系列南北向的輸送帶運送到bloggium精煉廠。

礦物非常不穩定,因此必須通過直線路徑運送到工廠,不能轉彎。這意味著如果一個單元格中有南北向輸送帶,但其北邊的單元格中有東西向輸送帶,那麼任何在南北向輸送帶上運輸的礦物都會丟失。特定單元格中開採的礦物必須立即放在同一單元格的輸送帶上(因此不能從相鄰的單元格開始運輸)。此外,任何運送到yeyenum精煉廠的bloggium都會丟失,反之亦然。

你的程序必須設計一個輸送帶系統,最大化所開採礦物的總量,即運送到yeyenum精煉廠的yeyenum和運送到bloggium精煉廠的bloggium的總和。

Input

輸入包含多個測試案例塊。每個案例以一行開始,包含兩個整數:行數 1 ≤ n ≤ 500 和列數 1 ≤ m ≤ 500。接下來的 n 行描述了單元格中可以找到的 yeyenum 數量。這 n 行中的每一行都包含 m 個整數。第一行對應於最北端的行;每行的第一個整數對應於該行最西端的單元格。這些整數介於 0 和 1000 之間。接下來的 n 行以類似的方式描述了單元格中找到的 bloggium 數量。

當出現 n = m = 0 的塊時,輸入結束。

Output

對於每個測試案例,你需要在單獨的一行上輸出一個整數:可以開採的礦物的最大數量。

Sample Input #1
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0
Sample Output #1
98
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
DP
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

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