Codeforces Round #715 The Sports Festival - DP

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:

  1. Last time, member $j$ already participated. This time, member $j+i-1$ participate. So $dp[i-1][j]+a[j+i-1]-a[j]$
  2. 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
DigitalOcean Referral Badge 蜀ICP备19018968号