Typical DP Contest F 準急

動的計画法

問題

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

方針

i番目の駅に止まり、i+1番目に止まらないような電車の止まり方の場合の数をdp[i]とする。
これを更新したいのだけれど、愚直にやるとO(nk)になってしまってダメ。



なので、dp[i] + dp[i-1] + dp[i-2] + … + dp[i-k+1]の部分和をsum[i]として、
これも同時に更新しながらDPする。


dp[i] = sum[i-1] + sum[i-2] + … + sum[i-k]であるため、
両端の新たに増える部分と減る部分だけを操作すればいい。
すると全体でO(n)で出来る。

ソースコード

const int mod = (int)1e9+7, MX = 1000100;
int n, k, dp[MX], sum2, sum[MX];


int main(){
	cin >> n >> k;
	
	dp[1] = sum[1] = 1;
	
	for(int i = 2; i <= n; i++){
		dp[i] = sum2 + (i < k);
		
		(sum2 += sum[i-1]) %= mod;
		if(i >= k) (sum2 += mod - sum[i-k]) %= mod;
		sum[i] = (sum[i-1] + dp[i]) % mod;
	}
	cout << dp[n] << endl;
	
	return 0;
}