北京建设局网站,温州网站建设及推广,上海专业排名优化公司,网站建设动态这道题最后有一个性质没有想出来#xff0c;感觉还是有一点遗憾。
性质一、贪心是不对的
8 11 11 16虽然第一次选择8和16合并是最优的#xff0c;但是如果合并两次的话8 11 11是最优的。
性质二 、有1的情况就是前k1个#xff0c;也就是说#xff0c;很多情况下取前k1都…这道题最后有一个性质没有想出来感觉还是有一点遗憾。
性质一、贪心是不对的
8 11 11 16虽然第一次选择8和16合并是最优的但是如果合并两次的话8 11 11是最优的。
性质二 、有1的情况就是前k1个也就是说很多情况下取前k1都是最优的
性质三 如果某个数前面有它的因子那么合并的时候可以不对 a 1 a_1 a1产生任何影响。同时如果 b m o d a 0 , b a b \mod a0,ba bmoda0,ba那么 b b b一定比 a a a后合并,也就是说无影响合并只会发生在相同的数之间因此我们把无影响的数提出来考虑所以剩下的都是不同的。
性质四 如果所有的数都不同那么全部都只会和 a 1 a_1 a1合并。在原来的数列中考虑合并形成的连通块。在连通块大小为2的情况时。设 a 1 x y a1xy a1xy那么有 y − x g c d ( x , y ) y-xgcd(x,y) y−xgcd(x,y)所以, x y − g c d ( x , y ) 2 x a 1 x xy-gcd(x,y)2xa_1x xy−gcd(x,y)2xa1x不如直接合并 a 1 a_1 a1和 x x x。现在考虑连通块大小超过2的情况。假设某个连通块不包含 1 1 1那么我们可以通过合并使得该联通块剩下两个数其中有一个还没有与任何的数合并。Case 1: x a 1 y xa_1y xa1y这时应该合并 x , a 1 x,a_1 x,a1最优与原假设矛盾。Case 2: a 1 x y a_1xy a1xy这时也是合并 a 1 , x a_1,x a1,x更优所以假设错误。
所以现在应该把前面有相同的和剩下的全部不同的数分成两个组然后给这两组分配合并次数难点就是要怎么求在给定的次数时全部不同组的选择方法但是我没有坚定的往这个方面想。
性质五 假设给全部不同的数合并 k k k次那么必然选择 1 , 2 , . . . , k − 1 1,2,...,k-1 1,2,...,k−1只有第 k k k个是不确定的。考虑选择 a , b , c , d ( a b c d ) a,b,c,d(abcd) a,b,c,d(abcd)的情况那么合并如果是 a , c , d a,c,d a,c,d的话那么 c o s t ( a , c , d ) − c o s t ( a , b , c ) d − b g c d ( a , c , d ) − g c d ( a , b , c ) g c d ( b , c ) g c d ( c , d ) g c d ( a , c , d ) − g c d ( a , b , c ) 0 cost(a,c,d)-cost(a,b,c)d-bgcd(a,c,d)-gcd(a,b,c)gcd(b,c)gcd(c,d)gcd(a,c,d)-gcd(a,b,c)0 cost(a,c,d)−cost(a,b,c)d−bgcd(a,c,d)−gcd(a,b,c)gcd(b,c)gcd(c,d)gcd(a,c,d)−gcd(a,b,c)0所以只用考虑第k个点怎么选而且枚举范围有 a [ i ] − a [ k − 1 ] g c d ( a 1 , a 2 , . . . , a k − 1 ) a[i]-a[k-1]gcd(a_1,a_2,...,a_{k-1}) a[i]−a[k−1]gcd(a1,a2,...,ak−1)这样显然是不超过 O ( n l o g n ) O(nlogn) O(nlogn)的。
