BZOJ 5068 友好的生物


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5068

题意:n 个物种,每个物种有 k 种属性,定义两种物种 a,b 的友好值为

$$friendliness_{a,b}=(\sum_{i=1}^{k-1}C_i\times \left | f_{a,i}-f_{b,i}\right |)-C_k \times \left | f_{a,k}-f_{b,k} \right |$$

其中,为了方便,记物种 i 的属性 j 为\(f_{i,j}\)。


这题做的时候只找到了一个 ppt 提到了它... 结果其中的伪代码貌似写错了所以没看懂...

这篇博客大概就是用我能看懂的话重述了一下陈启峰大爷的那篇论文,顺便给出了一个跑的挺快的代码实现。

 

暴力的复杂度是\(O(n^2\times k)\) 的,显然不能接受,于是考虑转化一下计算友好值的方式。

记 S 表示原始符号状态,即若 S 的第 i 位为 1,则有\(f_{a,i}\geq f_{b,i}\),方便起见记\(S_i\) 为 S 的第 i 位的值。

记\(F_{x,S}\) 表示物种 x 对答案的贡献,即

则此时转化\(friendliness_{a,b}=F_{a,S}-F_{b,S}\),其中 S 合法。

更新答案的过程可以转化为枚举 a 和 S,找到合法的最优的 b 更新答案,这个过程可以数据结构维护,但是时空和编程复杂度都无法接受。

 

更进一步


发现 k 的限制具有特殊性,每次寻找对于每个\(S_i\) 都合法的 b 太浪费了。考虑到转化限制,使得枚举时只满足\(S_k\) 合法即可,发现这么做得到的答案仍然是正确的。

为什么呢?

记集合\(S_1\) 为所有满足所有\(S_i\) 均合法的 S 组成的集合,此时答案的最大值为\(max_1\),\(S_2\) 为只要求\(S_k\) 合法的 S 组成的集合,此时答案最大值为\(max_2\)。

显然有\(S_1\subseteq S_2\),所以\(max_1\leq max_2\)

注意到有如下事实:对于任意的\(A,B\in R\),都有\(\left | A-B \right |\geq A-B\),\(\left | A-B \right |\geq B-A\) 成立。

观察原式:

$$friendliness_{a,b}=(\sum_{i=1}^{k-1}C_i\times \left | f_{a,i}-f_{b,i}\right |)-C_k \times \left | f_{a,k}-f_{b,k} \right |$$

发现在不考虑属性 k 的情况下,对答案贡献的每项都是\(\left | f_{a,i}-f_{b,i}\right |\) 形式的,即有

\(\left | f_{a,i}-f_{b,i}\right |\geq f_{a,i}-f_{b,i}\) 和\(\left | f_{a,i}-f_{b,i}\right |\geq f_{b,i}-f_{a,i}\) 成立

也就是说,尽管可能有一些\(S_i\) 不合法(即转换符号),但是一定不会比合法的更大。所以对于每个\(S \in S_2\) 计算出的值,均存在\(S' \in S_1\) 不小于它。

所以有\(max_1\geq max_2\),那么\(max_1 = max_2\)。

 

实现


按照属性 k 排序,顺序枚举即可保证\(S_k\) 合法。记录 max 更新答案即可。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 5068 友好的生物


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,