Typical DP Contest F - 準急

問題文 : 準急

解法 :
$dp[i][j] :=$ 駅$i$ までに$j$ 連続で止まる, というdp を考えると,
$dp[i][j] = dp[i - 1][j - 1]$ (if $j > 1$)
$dp[i][j] = \displaystyle \sum_{k = 0}^{i - 2} \sum_{l = 0}^{k - 1}dp[k][l]$ (if $j=1$)

となるのがわかるが, これを求めるのには$O(NK)$ 時間かかってしまいTLE.

まず, 後者は累積和を使うことで$O(1)$ で計算ができ, 前者は先頭に数が入ることと後ろから数が出るという状況しか起こりえないということからキューを使うことが出来る.

よって$O(N)$ 時間で計算可能である. (この実装ではキューの代わりにデックを使っている.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

int MOD = 1000000007;

using namespace std;

int sum[1000001], ssum[1000001];
deque<int> dp;
int main()
{
	int N, K;
	
	scanf("%d %d", &N, &K);
	
	int tsum = 1;
	ssum[1] = 1;
	sum[1] = 1;
	dp.push_back(1);
	for (int i = 2; i <= N; i++){
		dp.push_front(ssum[i - 2]);
		tsum = (tsum + ssum[i - 2]) % MOD;
		if (dp.size() >= K){
			tsum = (tsum - dp[dp.size() - 1] + MOD) % MOD;
			dp.pop_back();
		}
		
		sum[i] = tsum;
		ssum[i] = (ssum[i - 1] + sum[i]) % MOD;
	}
	
	printf("%d\n", sum[N]);
	
	return (0);
}