作者Ori185 (Ori185)
看板C_and_CPP
標題[問題] 高中生解題系統B568一問
時間Mon Sep 10 23:54:33 2018
開發平台(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1536594877.A.DCE.html
1F：推 idiont: 把n*700000變成2*700000 09/11 01:52
3F：→ idiont: 樓上這個不會過吧 09/11 12:29
4F：推 uorol: 題目不是最大只有100題嗎 09/11 13:09
5F：推 cateran: 用hash table? 09/11 16:25
6F：推 dou0228: 不是才 100 題？ 09/11 17:12
7F：→ Ori185: 不太懂各位的意思，如果最多100題，最大不就會創建100*70W 09/11 20:06
8F：→ Ori185: 的陣列嗎？ 09/11 20:06
10F：→ Ori185: 參照一樓的建議，已經不會有記憶體的問題了，可是4與5測稚 09/11 20:31
11F：→ Ori185: 還是差一點數字，請問哪裡有問題呢 09/11 20:31
12F：→ sarafciel: 你有考慮溢位後才會跳最大值的情況嗎 09/12 11:14
13F：→ sarafciel: 699999 3 699998 像這種測資超界就不算的會得到699999 09/12 11:18
14F：→ sarafciel: 但按題意他的最大值應該是699999+3+699998=700000 09/12 11:19
15F：推 alan23273850: 剛剛想了一下，如果針對每個數字多加一個負補數進去 09/12 13:46
16F：→ alan23273850: 例如 699999 就加個 -1，3 就加個 -699997，這樣會 09/12 13:47
17F：→ alan23273850: 形成一個 2 倍長度的陣列，如果題目轉成總和不超過 09/12 13:48
18F：→ alan23273850: 700000 的條件下要找到最大和，這樣是否就形成另類 09/12 13:48
19F：→ alan23273850: 的背包問題呢？值得注意的是因為原本的題目本來就都 09/12 13:48
20F：→ alan23273850: 是正整數，因此遇到 0 可以直接當成 700000 09/12 13:49
21F：推 alan23273850: 好像也不能當成背包問題，不過至少全部總共有 3^n個 09/12 13:53
22F：→ alan23273850: ... 好像也不太對 算惹 09/12 13:54
23F：→ Ori185: 感謝各位回答，回文的c大的程式碼已經AC過了，希望我趕快 09/13 23:44
24F：→ Ori185: 弄懂就是了… 09/13 23:44