题解 P1734 【最大约数和】

发表于 更新于 阅读次数： Waline：
P1734 【最大约数和】题解。

其实这题是个背包（我用暴力只得了20分）

S就是背包容量V，i就是重量，i的因子和就是价值。

这样一讲公式就出来了吧！

公式：

1
2
i为第一个数，j为第二个数，a[k]为k的因子和
dp[i]=max(dp[i-j]+a[j],dp[i]);

这个公式我想大家都能很方便地推出来。

接下来我要讲一讲本题一个很重要的优化，楼下们的代码中都或多或少的有，只是他们没有解释（大佬哪有时间解释）

于是，我这个蒟蒻就来解释一下吧！

本题一个很重要的优化就是：预处理！

1
2
3
4
void prime(){
    for (int i=1;i<=n;i++)
    for (int j=i*2;j<=n;j+=i)a[j]+=i;
}

看到这段预处理代码，有没有想到筛法？

没错，就是从筛法改过来的！

这个是筛法↓

1
2
3
4
5
6
7
8
9
10
11
12
bool s[10000]={1,1};//0和1啥都不是，定1！
int a[10000],ps;//a数组存最后的质数，ps为这个数组的下标
//全局数组初值全为0
inline void $(){//不要在意函数名，这只是个筛法函数
//财迷心窍的我
    for (int j=2;j<10000;j++)//暴力！汗！
    if (!s[j]){//s[j]=0，表明j不是合数（合数为1）
    a[ps++]=j;//纪录下j这个质数，下一个
    for (int k=j*2;k<10000;k+=j)//k=j*2省一个判断，每次+j，保证是j的倍数
    s[k]=1;//既然是j的倍数，那一定是合数，标记！
    }
}

我将筛法改了一下，就有了这个函数。

因为是要因子和，而合数因子也算在里面，所以不用判断质数，那个bool数组自然就不要了

j=i*2表示j初值为i的2倍，j+=i则保证j是i的倍数，就加上i这个因子

开始预处理到n，打好了一个动态表，接下来dp时就可以直接引用了

筛法的应用还有很多，所以，随机应变，打动态表可以节省很多时间哦！

代码我就不贴了，希望大家能明白预处理的重要性