アルゴリズムと数学 028

https://atcoder.jp/contests/math-and-algorithm/tasks/dp_a

単なるDPですね。

// Frog1
#![allow(non_snake_case)]

use std::cmp::min;

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_input() -> Vec<i32> {
    let _N: usize = read();
    let h = read_vec();
    h
}

fn f(h: Vec<i32>) -> i32 {
    let N = h.len();
    let mut dp = (0..N).map(|_| 0).collect::<Vec<i32>>();
    dp[1] = (h[1] - h[0]).abs();
    for i in 2..N {
        dp[i] = min(dp[i-2] + (h[i] - h[i-2]).abs(),
                    dp[i-1] + (h[i] - h[i-1]).abs())
    }
    dp[N-1]
}

fn main() {
    let h = read_input();
    println!("{}", f(h))
}