この問題は初心者向けの DP の問題です。

\(\mathrm{DP}[i]\) を地点 \(i\) にいる時点での疲労の合計の最小値とします。

地点 \(i\) に来る直前にいたのが地点 \(i-1\) か地点 \(i-2\) かを考えることで、

\(\mathrm{DP}[i]=\min(\mathrm{DP}[i-1]+\max(A_i-A_{i-1},0),\mathrm{DP}[i-2]+\max(A_i-A_{i-2},0))\)

となることがわかります。よって、この漸化式に従って計算することで求める答えである \(\mathrm{DP}[N]\) を \(O(N)\) で求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  vector<long long>dp(n);
  dp[0] = 0;
  dp[1] = max(a[1] - a[0], 0);
  for(int i=2; i<n; i++){
    dp[i] = min(dp[i-1]+max(a[i]-a[i-1],0), dp[i-2]+max(a[i]-a[i-2],0));
  }

  cout << dp[n-1] << endl;
}

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))
dp = [0] * N
dp[0] = 0
dp[1] = max(A[1] - A[0], 0)

for i in range(2, N):
  dp[i] = min(dp[i-1]+max(A[i]-A[i-1],0), dp[i-2]+max(A[i]-A[i-2],0))

print(dp[-1])

類題： EDPC A