P5336 [THUSC2016]成绩单

· · 题解

对本题的一种解法进行详细一点的解释。学习这道题时参考了 天梦（194093） 的题解，致以感谢。

 

一次可以抽出连续的一段，故考虑区间 DP。

设 f[l][r] 表示区间 [l,r] 被全部取走所需的最小代价，会发现信息不够，难以转移。

一次性取走一个区间所需的代价与且只与这个区间的最大值和最小值相关，所以不妨增设 g[l][r][\mathrm{mn}][\mathrm{mx}] 表示区间 [l,r] 取到剩余数最小值为 \mathrm{mn}，最大值为 \mathrm{mx} 所需的最小代价。可知这样 f 的转移即为：

f[l][r] = \min_{1 \le \mathrm{mn} \le \mathrm{mx} \le L}\{g[l][r][\mathrm{mn}][\mathrm{mx}] + A + B \cdot (\mathrm{mx} - \mathrm{mn})^2\}

这里 L 为最大可能的分数值。

接下来就该考虑 g 怎么转移了。g[l][r][\mathrm{mn}][\mathrm{mx}] 的意义是区间 [l,r] 被取走一些数，还剩下一些数，且这些数里最小值为 \mathrm{mn}，最大值为 \mathrm{mx}。那剩下这些数的情况，就可以划分成 \boldsymbol r 位置的数在这些数里（即 r 位置的数没有被取走） 和 \boldsymbol r 位置的数不在这些数里（即 r 位置的数被取走）这两种情况。

$$g[l][r][\min(\mathrm{mn},w_r)][\max(\mathrm{mx},w_r)] \gets g[l][r-1][\mathrm{mn}][\mathrm{mx}]$$ 这是因为，既然 $r$ 位置的数没有被取走，那么在 $[l,r-1]$ 区间取到剩余数最小值为 $\mathrm{mn}$，最大值为 $\mathrm{mx}$ 的操作，其在 $[l,r]$ 区间的效果就是取到剩余数最小值为 $\min(\mathrm{mn},w_r)$，最大值为 $\max(\mathrm{mx},w_r)$。 $r$ 位置的数被取走，则 $[l,r]$ 区间必然可以划分成一个 $[l,k]$ 区间和一个 $[k+1,r]$ 区间，满足 $k < r$，且 $[l,r]$ 区间没有被取走的数都在 $[l,k]$ 区间内（即 $[k+1,r]$ 区间所有数均被取走）。从而： $$g[l][r][\mathrm{mn}][\mathrm{mx}] = \min_{k=l}^{r-1}\{g[l][k][\mathrm{mn}][\mathrm{mx}] + f[k+1][r]\}$$ 这样，就得到了 $g$ 的转移。综合前面 $f$ 的转移，即解决本题。 &nbsp; 将数值离散化后，状态数和复杂度可以接受。