Divan and Kostomuksha (easy version)

2021-11-29

字数统计: 695字 | 阅读时长≈ 2分

题目大意

给定$n$个正整数$a_{1,2...n}$。

可以任意改变顺序。

求$gcd(a_1) + gcd(a_1,a_2)+...+gcd(a_1,a_2,...,a_n)$的最大值。

原题地址 ## 思路

直接求$gcd$时间复杂度肯定会炸。所以我们用$cnt[j]$表示因数包含$j$的数的个数,用这样的计算方式代替求$gcd$。

借助$cnt$数组计算

这个前缀$gcd$大小会逐渐下降的。

假设最开始$gcd$为$x$,那么对答案的贡献就是$x * cnt[x]$;

然后假设$gcd$下降到了$y$,那么可以推出$y | x$,即$ (x y = 0)$,我们来计算这一部分数的贡献,

因为实际上$cnt[y]$包含了$cnt[x]$,而$cnt[x]$已经被计算过了,

所以要减去它们,为$y * (cnt[y]-cnt[x])$。

DP

上述分析并不能解出本题,但帮我们了解了递推关系。

最优解法肯定与这种思路类似:把尽量大的,且与后面的数gcd大的数尽量放在前面。但是这么想是很难去推的,所以我们应该逆着来推:

假设最开始前面的数的$gcd$就是$1$,那么初始结果就是$n$,然后我们不断地把gcd大的数放在前面,计算这么做增大的部分。

假设最开始所有数的$gcd$均为$y$(实际上最开始我们是从$1$开始的),那么初始结果就是$cnt[y] * y$。
然后我们把所有$gcd$为$x$的数放在前面($y|x$),那么增加的结果改怎么计算呢？$cnt[x]$中的每个数在计算$cnt[y]$的贡献时,已经被计算了一次,所以我们应该计算它门多出来的部分,即$(x - y) * cnt[x]$。
然后我们再把$cnt[x]$中,$gcd$为$z(x | z)$的数放在前面,再次计算增加的数。

一直重复上述过程。

当然$gcd$可能会有很多个,我们并不能确定把哪个放在前面是最优的,所以此时我们就要用$DP$的做法了。

那么我们改动一下上述推算结果,状态转移方程就能写出来了

$dp[j] = max(dp[j], dp[i] + (j - i) * cnt[j])$,其中$i | j$。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 5e6;

int n;
long long dp[maxN + 10], cnt[maxN + 10];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
    }
    for(int i = 1; i <= maxN; ++i)
        for(int j = 2 * i; j <= maxN; j += i)
            cnt[i] += cnt[j];
    dp[1] = n;   
    long long ans = 0;     
    for(int i = 1; i <= maxN; ++i)
        for(int j = 2 * i; j <= maxN; j += i)
            dp[j] = max(dp[j], (j - i) * cnt[j] + dp[i]);
    for(int i = 1; i <= maxN; ++i)
        ans = max(ans, dp[i]);
    printf("%lld\n", ans);            
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/11/29/cf1614D1/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！

题目大意

借助\(cnt\)数组计算

DP

代码