Submission #4638184

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<ll, ll>;
template<class T> inline bool chmax(T& a, T b) {if (a < b){a = b;return 1;}return 0;}
template<class T> inline bool chmin(T& a, T b) {if (a > b){a = b;return 1;}return 0;}
const long long LLINF = 1LL << 60;
using namespace std;

ll dp[100001];
//
// ll solve(int i)
// {
//     if (i == 0) return 0;
//
//     ll res = LLINF;
//     chmin(res, solve(i-1) + abs(h[i] - h[i-1]));
//     chmin(res, solve(i-2) + abs(h[i] - h[i-2]));
//     return res;
// }

int main()
{
    int N;
    cin >> N;

    vector<ll> h(N);
    rep(i, N) cin >> h[i];

    // 初期化
    fill(dp, dp+N, LLINF);

    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for (int i=2; i<N; ++i)
    {
        dp[i] = min(dp[i-1] + abs(h[i-1] - h[i]), dp[i-2] + abs(h[i-2] - h[i]));
    }

    cout << dp[N-1] << endl;

    return 0;
}

Submission Info

Judge Result