※ 引述《DJWS (...)》之铭言： : ※ 引述《sophialiege (别忘了)》之铭言： : : Sorry for I only can type in English. : 没关系 如果有看不懂的单字 我可以查字典 :p 其实是因为我英文很破,写不清楚,现在我借一台可以打中文的电脑 : : The key point is we can jump from grid 'a' to grid 'b', if and only if : : the pennies 'a' possess more than that 'b' possess. : : For example, 1 ? ? k is 2 : : 4 2 5 : : 3 ? ? : : Assume we're now at (1,0) which has 4 pennies. : : By the capacity property, 1 2 5 3 is possible to move onto. : : By the property you ignored, only 5 is possible to move onto. : : The reason is 5 is larger than 4, current square pennies. : 我想到一个方法: : 开一个table, 用来纪录每一个位置的最大值. 初始值都是零； : 令 table[左上角] = 左上角那格的pennies; : while (只要有任何一个位置 a, 从这个位置可以合法的移动到 b : && table[a] + b的pennies > table[b] : && table[a] != 0 ) : { : table[b] = table[a] + b的pennies; : } : 找寻table的最大值, 即为答案； : 但是呢 我总觉得这个方法很没有效率 ^^" 不会吧@@ 这方法是O(kn^2)(至少我确定我的方法是O(kn^2)) 对於这一题k,n都不大於100 kn^2也只不过10^6 ...... 这样实在很小 这种类型的题目要弄成比较大的情况也有点困难 因为它需要不少的IO operation,弄不好说不定会让 重点落在IO的处理上,一般出题者不会做这种事 另外,我有过这一题,并不觉得这样的速度很慢,我是Ghost77,编号22305 : 这个方法就跟 BFS + memorization 差不多吧 : 也不像是DP 我演算法不好,王尹有回一篇,你和他讨论讨论吧 : 我想应该会有更好的方法吧 这一题应该可以对资料结构动手脚吧,重点在於尽量避免不必要的查看 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.250.176