ABC040_C

典型的DP問題

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int dp[MAX_N+1] = {0};//i本目の柱までにかかる最小コスト
    int n,x,height[MAX_N+1];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>height[i];
    }
    dp[1]=0;
    dp[2]=abs(height[2]-height[1]);
    for(int i=3;i<=n;i++){
        int a = dp[i-2] + abs(height[i-2]-height[i]);//柱i-2から柱iへのルート
        int b = dp[i-1] + abs(height[i-1]-height[i]);//柱i-1から柱iへのルート
        dp[i] = min(a,b);
    }
    cout<<dp[n]<<endl;
    return 0;
}