作者DJWS (...)
看板ACMCLUB
標題Re: [問題] 10259 Hippity Hopscotch
時間Thu Feb 24 23:04:23 2005
※ 引述《sophialiege (別忘了)》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 有人說這一題用DP可以做出來呢
: : 不過我卻想不出來
: : 有人可以提供一些想法嗎? 謝謝 ^^
: DP.
: try to remember each location's maximum pennies can be collected,
: (starting from the location)
我也是想到要去紀錄每一格的最大值
然而我看到了input range之後
最多會有100x100格
每次可移動的格子數 橫的和直的各會有100-1種走法
最多可以跳100次格子
如果用transitive closure的方法來做 時間相當驚人的多 =.=
: I think you haven't noticed the sentence.
: "That square must be within the jumping capability of the contestant
: (say, k locations) and must have more pennies than those that were
: on the current square."
從這句話我只看出了 "最多可以跳100次格子" 這個性質
我覺得這句話是個關鍵 攸關這個題目能不能用DP解決
只可惜我不知道要怎麼利用這個條件 :p
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.26.5