PTT數位生活區 / C_and_CPP (C/C++)

[問題] 高中生解題系統B568一問

看板C_and_CPP (C/C++)作者 (Ori185)時間7年前 (2018/09/10 23:54), 編輯推噓7(7推 0噓 17→)
留言24則, 7人參與, 7年前最新討論串1/3 (看更多)
開發平台(Platform): (Ex: Win10, Linux, ...) WIN10 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) g++ 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： https://zerojudge.tw/ShowProblem？problemid=b568 小弟我目前剛學到動態規劃演算法 看到這題似乎可以應用到便試了試 結果從第三個測資開始似乎因為超過限制的64MB而終止 認為應該有比起創立一個超級大的二維陣列以外(70萬…) 更加節省空間聰明的辦法 請問可以指點解一下嗎？ 非常謝謝 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔) https://glot.io/snippets/f4odl8o9kh/raw 補充說明(Supplement)： 記憶體限制64MB -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.213.186 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1536594877.A.DCE.html
推
09/11 01:52, 7年前 , 1F
把n*700000變成2*700000
09/11 01:52, 1F
推
09/11 10:44, 7年前 , 2F
09/11 10:44, 2F
→
09/11 12:29, 7年前 , 3F
樓上這個不會過吧
09/11 12:29, 3F
推
09/11 13:09, 7年前 , 4F
題目不是最大只有100題嗎
09/11 13:09, 4F
推
09/11 16:25, 7年前 , 5F
用hash table?
09/11 16:25, 5F
推
09/11 17:12, 7年前 , 6F
不是才 100 題？
09/11 17:12, 6F
→
09/11 20:06, 7年前 , 7F
不太懂各位的意思，如果最多100題，最大不就會創建100*70W
09/11 20:06, 7F
→
09/11 20:06, 7年前 , 8F
的陣列嗎？
09/11 20:06, 8F
→
09/11 20:30, 7年前 , 9F
09/11 20:30, 9F
→
09/11 20:31, 7年前 , 10F
參照一樓的建議，已經不會有記憶體的問題了，可是4與5測稚
09/11 20:31, 10F
→
09/11 20:31, 7年前 , 11F
還是差一點數字，請問哪裡有問題呢
09/11 20:31, 11F
→
09/12 11:14, 7年前 , 12F
你有考慮溢位後才會跳最大值的情況嗎
09/12 11:14, 12F
→
09/12 11:18, 7年前 , 13F
699999 3 699998 像這種測資超界就不算的會得到699999
09/12 11:18, 13F
→
09/12 11:19, 7年前 , 14F
但按題意他的最大值應該是699999+3+699998=700000
09/12 11:19, 14F
推
09/12 13:46, 7年前 , 15F
剛剛想了一下，如果針對每個數字多加一個負補數進去
09/12 13:46, 15F
→
09/12 13:47, 7年前 , 16F
例如 699999 就加個 -1，3 就加個 -699997，這樣會
09/12 13:47, 16F
→
09/12 13:48, 7年前 , 17F
形成一個 2 倍長度的陣列，如果題目轉成總和不超過
09/12 13:48, 17F
→
09/12 13:48, 7年前 , 18F
700000 的條件下要找到最大和，這樣是否就形成另類
09/12 13:48, 18F
→
09/12 13:48, 7年前 , 19F
的背包問題呢？值得注意的是因為原本的題目本來就都
09/12 13:48, 19F
→
09/12 13:49, 7年前 , 20F
是正整數，因此遇到 0 可以直接當成 700000
09/12 13:49, 20F
推
09/12 13:53, 7年前 , 21F
好像也不能當成背包問題，不過至少全部總共有 3^n個
09/12 13:53, 21F
→
09/12 13:54, 7年前 , 22F
... 好像也不太對 算惹
09/12 13:54, 22F
→
09/13 23:44, 7年前 , 23F
感謝各位回答，回文的c大的程式碼已經AC過了，希望我趕快
09/13 23:44, 23F
→
09/13 23:44, 7年前 , 24F
弄懂就是了…
09/13 23:44, 24F
‣ 更多 Ori185 的文章
文章代碼(AID): #1RbfEztE (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Ori185 的文章
文章代碼(AID): #1RbfEztE (C_and_CPP)