作者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