らての精進日記

修行をします

Typical DP Contest F:準急

解法

尺取法を用いて高速化したDPで解いた.
dp[i]:i番目の駅に止まらず,かつ条件を満たす組み合わせ.

とした.

実装を楽にするために,新たに0番目とN+1番目の駅を加えた.

1番目とN番目の駅には必ず止まらなければならないので,dp[1]=dp[N]=0である.
また,dp[0]=1とした.

具体的にどのようなDPをしているかというと,dp[i]+=dp[i-j]とするときは,i-j+1~i-1までの連続する駅に止まって,i-j番目とi番目の駅には止まらないという状態を数え上げている感じ.

つまり,dp[i]=dp[i-1]+dp[i-2]+...+dp[i-K+1]という更新をする.
これを普通にやるとTLEするから,尺取法(?)を使って少しずつずらした.

0番目の駅がdp配列に初期値を与える役割,N+1番目の駅が組み合わせを回収する役割(dp[N+1]が答えとなる)を担っている感じです.

(久々にそこそこ綺麗なコードを書きました)

コード

#include<bits/stdc++.h>
using namespace std;

int dp[1000010];
int N,K;
const int mod=1e9+7;
int main(){
    cin>>N>>K;

    dp[0]=1;
    int sum=1;
    for(int i=1;i<=N+1;i++){
        if(i!=1&&i!=N){
            dp[i]=sum;
            sum=sum*2%mod;
        }
        if(i-K>=0)sum=(sum-dp[i-K]+mod)%mod;
    }
    cout<<dp[N+1]<<endl;
    return 0;
}