yukicoder : No.595 登山

うーん、割と苦戦。
https://yukicoder.me/problems/no/595

問題

N個の山が順に並んでおり、各高さはH[i]である。
今1番の山におり、全山を最低1回到達した状態にしたい。最後どの山で終えても構わない。

山の間は以下の通り移動が可能である。

• 隣接する山に移動する。移動先の山の方が高い場合、高さの差分だけコストがかかる。
• 任意の山にワープする。固定コストPがかかる。

解法

各山の到達方法は

• 左の山からくる
• 右の山からくる
• ワープしてくる

のいずれかである。

これを考慮しつつ、1手先読みを行うDPで山の状態遷移をさせていこう。
状態は以下の３つとする。

1. 次に右に移動してもよい。上２つは次に移動する場所に関する状態だが、３つ目はどこから来るかに関する状態でちょっと異なるのに注意。
2. 次に左に行くことが決まっている。
3. 右から来られることを期待する。

左の山から状態別にDPし、コスト最小値を求めていく。

1. この状態になるには、左の山から移動してくるか、ワープしてくる必要がある。
2. この状態になるには、ワープしてくるか、次右から来られることを期待する必要がある。
3. この状態は、どの状態からでも遷移できる。

int N;
ll P,H[202020];
ll dp[3][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,N) cin>>H[i];
	
	dp[0][0]=dp[1][0]=dp[2][0]=0;
	// 0-free 1-non 2-req
	for(i=1;i<N;i++) {
		dp[0][i]=min(dp[0][i-1]+min(P,max(0LL,H[i]-H[i-1])), dp[1][i-1]+P);
		dp[1][i]=dp[2][i-1]+P+min(P,max(0LL,H[i-1]-H[i]));
		dp[2][i]=min({dp[0][i-1],dp[1][i-1],dp[2][i-1]+min(P,max(0LL,H[i-1]-H[i]))});
	}
	
	cout<<min({dp[0][N-1],dp[1][N-1]})<<endl;
}

まとめ

誤解法でWAを繰り返してしまった。