[NOIP2014]联合权值

这题在Vijos上难度8哈铪紦奤妎虾蝦鉿蛤

题目(vijos)

这题一开始稍微想复杂了……

其实思考一下就明白,距离为2的两个点之间一定有一个点(废话),

于是我们反过来想:连接在一个点上的不同的两个点一定距离为2。

所以,这题可以这样:

枚举每一个点,把连接在这个点上的点的权值用一个d数组记录下来。

然后对d数组从大到小排序,这样第一题就解决了:ans1=max(ans1,d[1]*d[2])。

第二问采用前缀和的方式解决:

比如连接在同一个点上的点的权值分别为1,3,5,6,

假设我们不考虑有序数对,那么总和为1*(3+5+6)+3*(5+6)+5*6,

明显可以用前缀和来优化。

答案为sum*2。

这题就解决了~

 

发表评论