Typical DP Contest F - 準急

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp

解法

dp[i][j] := i 番目の電車まで考えた時，右端が j である (j=0: 停車, j=1: 通過) 場合の数
として更新していく．
右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい．
停車する場合は，直前の K-1 回で停車し，かつ駅 1 から駅 i-1 までだけを考えれば条件を満たす場合の数を引く必要がある．
これは dp[i-K][1] で求まる．(直前 K-1 回が停車駅なら，駅 i-K では通過していなければならない)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll MOD = 1e9+7;

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<ll>> dp(N+1, vector<ll>(2));
    dp[0][0] = dp[0][1] = 1;
    for(int i=1; i<=N; ++i) {
        if(i == 1) {
            dp[1][0] = 1;
            dp[1][1] = 0;
            continue;
        }
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD;
        if(i - K >= 0) {
            dp[i][0] = (dp[i][0] - dp[i-K][1] + MOD) % MOD;
        }
    }
    cout << dp[N][0] << endl;
}