作者DJWS (...)
看板ACMCLUB
標題Re: [問題] 10259 Hippity Hopscotch
時間Fri Feb 25 18:23:24 2005
※ 引述《sophialiege (別忘了)》之銘言：
: : 但是呢 我總覺得這個方法很沒有效率 ^^"
: 不會吧@@ 這方法是O(kn^2)(至少我確定我的方法是O(kn^2))
: 對於這一題k,n都不大於100
: kn^2也只不過10^6 ...... 這樣實在很小
: 這種類型的題目要弄成比較大的情況也有點困難
: 因為它需要不少的IO operation,弄不好說不定會讓
: 重點落在IO的處理上,一般出題者不會做這種事
: 另外,我有過這一題,並不覺得這樣的速度很慢,我是Ghost77,編號22305
: : 這個方法就跟 BFS + memorization 差不多吧
: : 也不像是DP
: 我演算法不好,王尹有回一篇,你和他討論討論吧
: : 我想應該會有更好的方法吧
: 這一題應該可以對資料結構動手腳吧,重點在於盡量避免不必要的查看
我剛剛用了DFS with memorization
雖然跑了5秒鐘 可是還是accepted了
很幸運阿 ^^
或許用BFS就可以跑快一點了
我看到好多人都在一秒內呢..真厲害
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.26.5