2010JOI春合宿1-3 Stairs 解説

問題リンク

解説

動的計画法を適切に高速化する問題です。

を、 番目の階段に来る方法の総数とします。

を求めるとき、どこの階段からここまで上ってこられるかを考える。これは、尺取り法や二分探索を使えば高速に求められます。 そのような段のうち最も低いものの index を とすると、 から までの総和が求められればよいです。 これは累積和を求めておくことで実現できます。

このように、累積和などでDPが高速化できることは多いので、高速化できる部分に気づく必要があることもあります。