C - 柱柱柱柱柱時間制限 : 2sec / メモリ制限 : 256MB

問題文 N 本の木の柱が左から右へ一列に並んだアスレチックがあります。左から i 本目の柱の高さは ai センチメートルです。

高橋君は左から 1 本目の柱からスタートし、右へ柱を渡っていき N 本目の柱まで行こうとしています。

高橋君がある柱にいるとき、次には現在の柱から 1 個もしくは 2 個右にある柱のどちらかへ移動することができます。

移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。

N 本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。

制約 2≦N≦100,000 0≦ai≦10,000 ai はすべて整数である。

note

動的計画法つかうだけだぽん

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

#define N_MAX 100001
#define A_MAX 10001
#define MOD 1000000007
#define ll long long

using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    int n;
    ll a[N_MAX];
    ll dp[N_MAX];
    Fill(dp, N_MAX * A_MAX);
    dp[0] = 0;

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

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

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

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 040 #33

note