Codeforces Round #715 The Sports Festival - DP

题意

给你一个长度为$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
展示评论