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; }