作者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/cn.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