算法

(状态机dp) $\mathcal{O}(n)$

记 dp[i][0] 表示在第 $i$ 个位置选 $a_i$ 的最小代价，dp[i][1] 表示在第 $i$ 个位置选 $b_i$ 的最小代价

初态：$dp[1][0] = dp[1][1] = 0$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    vector<ll> dp(2);
    rep(i, n-1) {
        vector<ll> old(2);
        swap(dp, old);

        dp[0] = min(old[0]+abs(a[i+1]-a[i]), old[1]+abs(a[i+1]-b[i]));
        dp[1] = min(old[0]+abs(b[i+1]-a[i]), old[1]+abs(b[i+1]-b[i]));
    }

    ll ans = min(dp[0], dp[1]);
    cout << ans << '\n';

    return 0;
}