TopCoder SRM 814 : Div1 Easy Div2 Hard StepLeapSurviveTraps

なんでこんなド典型が出てきたんだろう。
https://community.topcoder.com/stat?c=problem_statement&pm=17217&rd=18888

問題

0～N番の(N+1)マスが順に並んでいる。
0番のマスから初めて、1～J番進んだマスに移動する、ということを繰り返し最終的にN番のマスに到達したい。
その際、i番のマスを踏むとT[i]だけコストがかかる。
総コストを最小化せよ。

解法

f(i) := i番のマスに到達する際の総コスト
とすると、f(i)=T[i] + min(f(i-J), f(i-(J-1)), ..., f(i-1))となる。
minの中身はRMQまたはスライド最小値で計算可能。

ll T[505050];
ll dp[505050];
class StepLeapSurviveTraps {
	public:
	long long minDamage(int N, int J, int seed, int M) {
		T[0] = 0;
		ll state = seed;
		int i;
		deque<int> D;
		D.push_back(0);
		dp[0]=0;
		
		for(i=1;i<=N;i++) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
			T[i]=1+state%M;
			while(D.front()<i-J) D.pop_front();
			dp[i]=T[i]+dp[D.front()];
			while(D.size()&&dp[D.back()]>=dp[i]) D.pop_back();
			D.push_back(i);
		}
		return dp[N];
	}
}

まとめ

問題不足なのかな…。