Algoogle

Algorithm for Programming Contest

Typical DP Contest F - 準急

Category: TDPC Tag: dp

F - 準急

問題概要


解法


止まらない駅の組み合わせを考える. 駅の幅を両側に一つずつ伸ばしてとして駅N+1で止まらない場合の数を考える.
駅1,Nは止まるので0.
i番目の駅で止まらない場合の数は, 最後に止まらなかった場所の場合の数の総和
K駅以上連続で止まってはいけないので,この場合

部分和なのであらかじめそれまでの合計を算出しておく.
i=1とi=Nの場合は無視する.

コード


(F.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#define int long long
#define repi(i,a,b) for(int i = (a); i < (b); i++)
const int mod = 1000000007;
int N, K;
int dp[1000010]; //cases that not stop station k
int sum[1000010];

void input(){ cin >> N >> K; }

int solve(){
    dp[0] = sum[1] = 1;
    repi(i,1,N+2){
        if(i != 1 && i != N)dp[i] = (sum[i] - sum[max(i-K, 0LL)] + mod) % mod;
        sum[i+1] += dp[i] + sum[i];
        sum[i+1] %= mod;
    }
    return dp[N+1];
}

signed main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments