题解

思路

先把价值中的对角项与无序点对分开。对角项恰好抵消，任意两个被选位置 $x<y$ 对答案的贡献是

$$a_x+a_y-2\min_{x\le k\le y}a_k.$$

建立序列的最小笛卡尔树：中序遍历顺序为原下标，父亲的权值小于儿子的权值。位置 $x,y$ 在树上的最近公共祖先，正是区间 $[x,y]$ 的最小值位置。因此上式等于树上 $x,y$ 两点的加权距离，其中父子边 $(u,v)$ 的边权为 $a_v-a_u$。原问题转化为：在一棵加权树中选择恰好 $m$ 个点，使两两距离之和最大。

若一条父子边下方的子树中选了 $j$ 个点，则恰有 $j(m-j)$ 对被选点的路径经过这条边，所以该边贡献为

$$(a_v-a_u)j(m-j).$$

子任务一

当 $n\le20$ 时，枚举大小为 $m$ 的下标集合，预处理所有区间最小值后直接计算每个集合的价值。

子任务二

当 $m=2$ 时，只需枚举两个位置。固定左端点并向右移动右端点，同时维护区间最小值，即可求出所有点对的最大贡献。

子任务三

当 $a$ 严格递增时，区间最小值总是左端点值。若某个数是所选子序列中的第 $j$ 个，它在所有点对中的系数为

$$(j-1)-(m-j)=2j-m-1.$$

于是用 $dp_{i,j}$ 表示扫描前 $i$ 个数并选择 $j$ 个的最大值，枚举是否选择 $a_i$ 即可。

满分做法

先用单调栈在线性时间内建立最小笛卡尔树。设 $dp_{u,k}$ 表示在 $u$ 的子树中选择 $k$ 个点时，子树内部所有边产生的最大贡献。初始可以不选或只选结点 $u$，均为 $0$。

依次合并儿子 $v$。若合并前在已处理部分选 $i$ 个、在 $v$ 子树选 $j$ 个，则转移为

$$dp'_{u,i+j}=\max\left(dp'_{u,i+j},dp_{u,i}+dp_{v,j}+(a_v-a_u)j(m-j)\right).$$

最后根结点的 $dp_{root,m}$ 就是答案。

做法

1. 用单调递增栈构造最小笛卡尔树，并记录左右儿子。
2. 迭代得到树的后序遍历，避免链状树导致递归栈溢出。
3. 按后序遍历执行树形背包，所有状态只保留到 $m$。
4. 输出根结点选择 $m$ 个点的状态值。

复杂度

子任务一的时间复杂度为 $O\!\left(\binom{n}{m}m^2+n^2\right)$，空间复杂度为 $O(n^2)$。

子任务二的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

子任务三的时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。

满分做法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(nm)$。