読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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;
}