|
发表于 2023-6-10 09:51:04
|
显示全部楼层
我有了一个思路,但是懒得写代码了
首先,如果选择所有数,那么最终的结果就应该是 a1 + ... + an + gcd(a1, ... , an),但如果选了 al ~ ar, 结果就变成了al + ... + ar + gcd(al, ..., ar)
如果要找到结果最大,无非有两种选择:一是选择全部的数,二是选择一部分使 gcd 变大。若 al + ... + ar + gcd(al, ..., ar) > a1 + ... + an + gcd(a1, ..., an),则
两边同时减去 (al + ... ar),gcd(al, ..., ar) > a1 + ... + al-1 + ar+1 +... +an + gcd(a1, ..., an)
又因为 min(al, ..., ar) > gcd (al, ..., ar) > a1 + ... + al-1 + ar+1 +... +an + gcd(a1, ..., an) > a1 + ... + al-1 + ar+1 +... +an > max(a1 , ... , al-1 , ar+1 ,... ,an)
所以 我们选择的数中的最小值 应当大于 未选择的数中的最大值,即我们要选择前(r-l+1)大的数。
由此一切都变得明了了,我们只需要先把全部选择的结果算出来,然后对所有数进行一个排序,依次选择前1大、前2大……前n大(一次增加一个)的数,看他们是否能够连接成一个区间(也就是max(原索引) - min(原索引) = 选择数的数量-1),对能够连成区间的进行计算。
此外,当我们选择的前 x 大的数的 gcd 已经等于 原数列所有数的 gcd 时,可以直接进行剪枝,并跳出循环。 |
|