Solution:
Sort $a$ first.
We can easily find that on any day, the members inside must be a continuous segment of $a$.
For example, for $(1,2,4,6,7)$. If the first member is 4. Then the second member must be one of 2 or 6. If the second member is 6, then the third member must be one of 2 or 7.
So we can let dp[i][j] to represent the minimum $d_i$ which start from member $j$.
So $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])$.
Which means: $dp[i][j]$ must be one of the case blow:
- Last time, member $j$ already participated. This time, member $j+i-1$ participate. So $dp[i-1][j]+a[j+i-1]-a[j]$
- Last time, member $j$ not participated. This time member $j$ participate. So $dp[i-1][j+1]+ a[j+i-1]-a[j]$.
The minimum value of $dp[n][?]$ is the answer.
Code:
Submission #113257955 - Codeforces
Codeforces. Programming competitions and contests, programming community
