※ 引述《DJWS (...)》之铭言： : ※ 引述《sophialiege (别忘了)》之铭言： : : 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 Sorry for I only can type in English. 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. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.250.175