ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Typical DP Contest F - 準急

問題
提出コード

解法

dp[i] = iで止まるような駅iまでのパターン数、のようにしていきたいところですが、連続して何駅止まったか、という情報が必要になるので無理です。
逆転の発想をして、dp[i] = iを通過するような駅0i-1のパターン数、としましょう。
ダミーの駅0というものが存在し、ここを必ず通過している、と仮定します。初期状態では、dp[0] =1、そしてdp[1] = 0です。
iで通過するには、駅i-1を通過している、駅i-1にはとまるが駅i-2で通過している、駅i-1と駅i-2にはとまるが駅i-3で通過している…駅i-1から駅i-K+1にはとまるが駅i-Kで通過している、というパターンがあります。
結局はこのようになります。
\displaystyle dp[i] = \sum_{j=min(0,i-K)}^{i-1} dp[j]
これは、累積和なりを用いることで、簡単に計算することができます。
あとは、答えを求めるだけです。
Nにはとまらなければならないので、駅N-1を通過している、駅N-2を通過してそれ以降とまる、駅N-3を通過してそれ以降とまる、…駅N-K+1を通過してそれ以降とまる、というパターンの総和になります。ここで、駅Nはとまる必要があるので、先ほどと条件が少しことなることに注意してください。
ということで、答えは以下のようになります。
\displaystyle \sum_{j=N-K+1}^{N-1} dp[j]
あとは、10^{9}+7で割った余りをとることに注意しつつ計算していけばよいです。