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