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