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