Codeforces Round #715 (Div. 2) C-The Sports Festival

​​傳送門​​ The student council is preparing for the relay race at the sports festival.

The council consists of n members. They will run one after the other in the race, the speed of member i is si. The discrepancy di of the i-th stage is the difference between the maximum and the minimum running speed among the first i members who ran. Formally, if ai denotes the speed of the i-th member who participated in the race, then di=max(a1,a2,…,ai)−min(a1,a2,…,ai).

You want to minimize the sum of the discrepancies d1+d2+⋯+dn. To do this, you are allowed to change the order in which the members run. What is the minimum possible sum that can be achieved?

Input

The first line contains a single integer n (1≤n≤2000) — the number of members of the student council.

The second line contains n integers s1,s2,…,sn (1≤si≤109) – the running speeds of the members.

Output

思路：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
#define ll long long     
ll a[2010];
ll dp[2010][2010];

int main()
{
  int n;
  cin>>n;
  for(int i = 1; i <= n; i++)
  {
    cin>>a[i];
  }
  sort(a+1,a+1+n);
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j+i-1 <= n; j++)
    {
      int end = j+i-1;
      dp[j][end] = min(dp[j+1][end], dp[j][end-1])+a[end]-a[j];
    }
  }
  printf("%lld\n",dp[1][n]);
}