※ 引述《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