位於休斯頓的NASA太空中心距離德克薩斯州聖安東尼奧(今年ACM總決賽的地點)不到200英里。這裡是宇航員訓練進行“七個小矮人任務”的地方,這是太空探索的下一次巨大飛躍。火星奧德賽計劃揭示了火星表面富含yeyenum和bloggium。這些礦物是某些革命性新藥的重要成分,但在地球上極為稀有。“七個小矮人任務”的目標是在火星上開採這些礦物並將它們帶回地球。
火星奧德賽探測器確定了火星表面一個富含礦物的矩形區域。該區域被劃分為n行m列的網格,其中行從東到西,列從北到南。探測器確定了每個單元格中yeyenum和bloggium的含量。宇航員將在矩形區域的西部建造yeyenum精煉廠,在北部建造bloggium精煉廠。你的任務是設計一個輸送帶系統,讓他們能夠開採到最多的礦物。
有兩種類型的輸送帶:第一種將礦物從東向西運輸,第二種將礦物從南向北運輸。在每個單元格中,你可以建造任意一種類型的輸送帶,但不能在同一單元格中建造兩種輸送帶。如果相鄰的兩個單元格有相同類型的輸送帶,它們可以連接。例如,一個單元格中開採的bloggium可以通過一系列南北向的輸送帶運送到bloggium精煉廠。
礦物非常不穩定,因此必須通過直線路徑運送到工廠,不能轉彎。這意味著如果一個單元格中有南北向輸送帶,但其北邊的單元格中有東西向輸送帶,那麼任何在南北向輸送帶上運輸的礦物都會丟失。特定單元格中開採的礦物必須立即放在同一單元格的輸送帶上(因此不能從相鄰的單元格開始運輸)。此外,任何運送到yeyenum精煉廠的bloggium都會丟失,反之亦然。
你的程序必須設計一個輸送帶系統,最大化所開採礦物的總量,即運送到yeyenum精煉廠的yeyenum和運送到bloggium精煉廠的bloggium的總和。
輸入包含多個測試案例塊。每個案例以一行開始,包含兩個整數:行數 1 ≤ n ≤ 500 和列數 1 ≤ m ≤ 500。接下來的 n 行描述了單元格中可以找到的 yeyenum 數量。這 n 行中的每一行都包含 m 個整數。第一行對應於最北端的行;每行的第一個整數對應於該行最西端的單元格。這些整數介於 0 和 1000 之間。接下來的 n 行以類似的方式描述了單元格中找到的 bloggium 數量。
當出現 n = m = 0 的塊時,輸入結束。
對於每個測試案例,你需要在單獨的一行上輸出一個整數:可以開採的礦物的最大數量。
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
98
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|