https://yukicoder.me/problems/no/595
解法
https://yukicoder.me/submissions/216410
公式解説がとても詳しい。
以下、それと同じことを違う言葉で説明する。
dpをする。
dp[i][dir] := i番目(0-indexed)の頂点にいてdir向き(=0:→, =1:←)の区間にいる途中の最小コスト
初期化はdp[0][0]=0, dp[other]=INFとする。
dp[i][0],dp[i][1]からの遷移は4種類考えられるので、それをやる。
- ->を伸ばす遷移
- これは横に伸ばすだけなので、普通にコストを足す
- しかし、コストよりもワープコストの方が小さいなら、ワープで移動する
- dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + min(P, max(H[i + 1] - H[i], 0LL)));
- 今まで->だったのを<-とする遷移
- ワープしないと移動できないので、ワープコストだけかかる
- dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + P);
- <-を伸ばす遷移
- 「->を伸ばす遷移」と同様
- dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + min(P, max(H[i] - H[i + 1], 0LL)));
- 今まで<-だったのを->とする遷移
- これも「今まで->だったのを<-とする遷移」と同様
- dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + P);
あとは、dp[N-1][0]とdp[N-1][1]の小さいほうが答え。
これは最終的な終了地点はどこでもいいからである。
typedef long long ll; #define INF 1LL<<60 int N; ll P, H[201010]; ll dp[201010][2]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> P; rep(i, 0, N) cin >> H[i]; rep(i, 0, 201010) rep(dir, 0, 2) dp[i][dir] = INF; dp[0][0] = 0; rep(i, 0, N - 1) { // ->を伸ばす遷移 dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + min(P, max(H[i + 1] - H[i], 0LL))); // 今まで->だったのを<-とする遷移 dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + P); // <-を伸ばす遷移 dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + min(P, max(H[i] - H[i + 1], 0LL))); // 今まで<-だったのを->とする遷移 dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + P); } ll ans = min(dp[N - 1][0], dp[N - 1][1]); cout << ans << endl; }