首先 $c$ 没什么卵用,我们直接把他乘到属性里。

可以发现这里的 $d$ 是两个属性值减一减的绝对值,所以我们要考虑怎么维护这个绝对值。

我们先考虑 $K = 1$ 的情况,先把这些生物按照 $d$ 的大小排个序,那么后一个减前一个的值一定就是非负的,也就等于绝对值,直接扫一遍就好了。

接下来考虑 $K \not = 1$ 的时候的前 $K - 1$ 位,根据幼儿园学过的知识我们可以知道:

$$a - b \leq |a -b|$$

由于我们要求绝对值的和的最大值,所以我们只要枚举每个属性的正负把他们一起取最大值即可。

那么第 $K $ 位怎么办呢?我们可是要加上绝对值的相反数啊。没关系,采用之前 $K = 1$ 的时候的方法,减一减扫过去,就能保证你去到的值非负啦。

这题需要用到一个惯用的套路。

$$a - b \leq |a - b|$$

显然如果是 $a - b$ 非负的,直接取等号;如果 $ a - b $ 负数,那么绝对值就是正数,负数一定小于正数。

考虑到 $ 2 ^ 5 ​$ 并不是很大,我们可以暴力枚举每个数的符号(用状态压缩的方式)。然后维护一棵线段树进行修改和查询即可。

非常妙的一道状压题。

考虑依次加入每一个点,状态之间的转移和对答案的贡献只与每个深度的节点个数,因此我们可以这样定义状态:把这棵树的节点按深度排序,显然相邻两个的深度最多相差一,如果差等于一,状压出的对应位就是 1 ,否则就是 0 。利用这个即可进行 $O(2^n \times n ^ 2)$ 的转移。

还有一种 $O(n ^ 3)$ 的天顶星写法,但是我暂时不会,只能等以后补锅。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×