题意
给你一个长度为$n$的数组$a$。定义$d_i=max(a_1,a_2,...,a_i)-min(a_1,a_2,...,a_i)$。问你最小的$\sum_{i=1}^{n}d_i$是多少。
题解
首先对$a$排序。
我们可以很容易的发现，任意一天，里面的成员一定是$a$中连续的一段。
比如说$(1,2,4,6,7)$。如果我们第一天选了4，那么第二天必然在2，6中选一个。如果第二天选了6，那么第三天必然在2，7中选一个。
于是我们定义$dp[i][j]$表示，从$j$开始，选择长度为$i$的区间，最小的$d_i$的值。
于是有$dp[i][j]=min(dp[i-1][j]+a[j+i-1]-a[j], dp[i-1][j+1]+ a[j+i-1]-a[j])$。
意思是，$dp[i][j]$要么是上次就已经让$j$参与，这次让$j+i-1$新参与进来，也就是$dp[i-1][j]+a[j+i-1]-a[j]$。要么就是上次没让$j$参与，这次让$j$参与进来，也就是dp[i-1][j+1]+ a[j+i-1]-a[j]。
于是$dp[n][?]$中的最小值就是答案。
代码
Submission #113257955 - Codeforces
Codeforces. Programming competitions and contests, programming community
