Typical DP Contest F : 準急

問題リンク：

F: 準急 - Typical DP Contest | AtCoder

解法：
dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1]
初期値は dp[0] = 1, dp[1] = 0
また、dp[N] = 0
dp[1]=dp[N]=0は、必ずその駅にとまることを意味する
dp[i]は
max(0,i-K)駅では停車せず、開区間(max(0,i-K),i)の各駅で停車する総数と
....
(i-2)駅では停車せず、(i-1)駅で停車する総数と
閉区間[max(0,i-K),i]のどの駅にも停車しない総数の和として表される
愚直に数えると間に合わないのでdpの総和を持っておく

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL;
const int MAX = 1000010;
ll dp[MAX];
int N,K;

int main() {
dp[0] = 1;
dp[1] = 0;
cin >> N >> K;
/*-- debug
REP(i,2,N+2) {
if( i == N ) { dp[i] = 0; continue; }
for(int j=max(0,i-K);j<i;j++) {
( dp[i] += dp[j] ) %= mod;
}
}
cout << dp[N+1] << endl;
debug -- */

ll sum = 1;
REP(i,2,N+2) {
if( i == N ) {
dp[i] = 0;
} else {
dp[i] = sum;
( sum += dp[i] ) %= mod;
}
if( i - K >= 0 ) { sum -= dp[i-K]; while( sum < 0LL ) sum += mod; }
}
cout << dp[N+1] << endl;
return 0;
}