Codeforces Round #715 Div. 2C The Sports Festival: 区間DP典型 - Qiita

区間DPの超典型。以下、0-indexed。 この問題の難しさ 入力をソートして、どこからかスタートし、最適に左右にとり続ければよいことがわかるが、これでは、ある地点をスタートして、左右どちらに行くかを計算するため、$O(2000*2^{2000})$のオーダーとなる。 アプローチ まず、入力をソートしてn個の要素を$a_0, a_1, ..., a_{n-1}$とする。 ある区間$[l, r)$の最善なコストを$dp[l, r)$と表す。この時、求めたい結果は$dp[0, n)$である。ただし、題意より、$dp[x, x+1) = 0$である(つまり、ある１つの数を選んでいるとき)。 この時、$dp[l, r) = min ((a_r - a_l) + dp[l+1, r), dp[l, r+1) + (a_r - a_l))$である。つまり、 ある区間のコストとは、それより1つ短いコス