題目大意

有個序列 $a_1, a_2, \ldots, a_n$，目標是經過某些操作把它變成 $b_1, b_2, \ldots, b_n$。每一次可以進行的操作是：選一個 $i$，然後把當前的 $a_i, a_{i+1}, \ldots, a_n$ 全部同時 $+1$ 或 $-1$。輸出最少的步數。

題解

注意到

  1. 在解答中任意變換操作順序，仍然不影響加總結果。
  2. 在最少的步數下，$a_1$ 只有一種方法可以變成 $b_1$，而且必定花費 $\vert b_1-a_1\vert$ 步。

因此由 1. 我們可以只考慮那些按照註標遞增順序的那些操作序列。再由 2. 我們可以依序遞推每一個「當前」的 $a_i$ 需要經過幾的操作，於是就可以得出答案啦。

參考程式碼

// by tmt514
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
using namespace std;
typedef long long LL;

const int N = 200005;
int a[N], b[N];

int main(void) {
  int n;
  scanf("%d", &n);
  for(int i=0;i<n;i++) scanf("%d", &a[i]);
  for(int i=0;i<n;i++) scanf("%d", &b[i]);
  long long ans = 0, cur = 0;
  for(int i=0;i<n;i++) {
    ans += abs(a[i]+cur - b[i]);
    cur = b[i]-a[i];
  }
  cout << ans << endl;
  return 0;
}