最小費用流で解くことを考えます。
頂点 \(S, T, U_1, \dots U_N, V_1, \dots V_N\) をとります。\(BIG\) を十分大きい定数とします。

• \(S\) から \(U_i\) へ、容量 \(1\)、コスト \(C\) の辺 \((1 \leq i \leq N)\)
• \(U_i\) から \(V_i\) へ、容量 \(1\)、コスト\(-BIG\) の辺 \((1 \leq i \leq N)\)
• \(V_i\) から \(T\) へ、容量 \(1\) 、コスト \(0\) の辺 \((1 \leq i \leq N)\)
• \(V_i\) から \(U_j\) へ、容量 \(1\)、コスト\(|A_i - A_j|\) の辺 \((1 \leq i \lt j \leq N)\)
• \(S\) から \(T\) へ、容量 \(N\)、コスト\(0\) の辺
  

を張ります。
すると、\(S\) から \(T\) への流量 \(N\) の最小費用流のコストに \(BIG*N\) を加えたものが、答えになります。

このままだと負のコストの辺があるので、流量が一定であることを利用して負のコストの辺を取り除くことを考えます。
具体的には、まず頂点 \(S', T'\) を用意し、

• \(U_i\) から \(V_i\) への、容量 \(1\)、コスト\(-BIG\) の辺 \((1 \leq i \leq N)\)

を削除し、

• \(S'\) から \(V_i\) へ、容量 \(1\) 、コスト \(0\) の辺 \((1 \leq i \leq N)\)
• \(V_i\) から \(U_i\) へ、容量 \(1\) 、コスト \(BIG\) の辺 \((1 \leq i \leq N)\)
• \(U_i\) から \(T'\) へ、容量 \(1\) 、コスト \(0\) の辺 \((1 \leq i \leq N)\)
• \(S'\) から\(S\) へ、容量 \(N\) 、コスト \(0\) の辺
• \(T\) から\(T'\) へ、容量 \(N\) 、コスト \(0\) の辺

を張ります。
このグラフにおける流量 \(2N\) の最小費用流のコストが求める答えになります。