公式解説と同じく最小費用流です。

頂点 \(S, T, U_1, \ldots, U_N, V_1, \ldots, V_N\) をとります。

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

を張ります。このネットワークにおける、\(T\) から\(S\) への流量 \(N\) の最小費用流が答えです。

この張り方は公式解説のグラフから変形することで得られます。 それを示します。

公式解説のグラフは、頂点集合がこの解説のグラフと同じで、辺が以下でした:

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

これの \(S\) から\(T\) への流量 \(N\) の最小費用流に \(BIG \times N\) を足したものが答えでした。 ここで、\(S\) から \(T\) へのすべてのパスのコストが \(C\) だけ少なくなれば、最小費用流は \(N \times C\) だけ少なくなります。これは \(S\) から \(U_i\) への辺のコストを \(C\) から \(0\) に、\(S\) から \(T\) への辺のコストを \(0\) から \(-C\) に変更することで実現できます。

公式解説のグラフと比べ、最小費用流が \(N \times C\) だけ小さい、以下のようなグラフができました。

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

ここで、\(S\) から \(T\) へ \(2 \times N\) だけ流すことにします。\(S\) から \(T\) への流量を \(N\) にするためには、この状態で \(T\) から \(S\) に \(N\) だけ流す必要があります。流すときのパスについてですが、\(S \to U_i \to V_i \to T\) に \(1\)、\(S \to T\) に \(N\) だけ流すことにすれば、負のコストを持つ辺が消えます。この流しでコストに \(N \times (C + BIG)\) が加わります。

フローを \(2 \times N\) だけ流して逆辺を追加した残余ネットワークは以下のようになります。公式解説のグラフの最小費用流と比べ、\(N \times BIG\) だけ大きいです。

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

このグラフは、この解説のグラフと、辺 \(V_i \to U_i\) の有無を除けば同一です。辺 \(V_i \to U_i\) のコストは \(BIG\) であり十分大きかったので、最小費用流として選ばれようもないため、結局この解説のグラフと等価であることがわかりました。