题目描述
如果一个数 x 的约数和 y （不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。例如 4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
输入格式
输入一个正整数 n。
输出格式
输出不断进行数字变换且不出现重复数字的最多变换步数。
样例
样例输入
7样例输出
3样例说明
一种方案为 4→3→1→7。
数据范围与提示
对于 100% 的数据，1≤n≤50000。
******求树的最长链问题，先预处理每个数的约数，将可以互相转化的数之间连边，很明显这是一颗树，我们要求树的最长路径。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int sum[] = {},n,d1[],d2[];
void ready()
{
int i,j;
scanf("%d",&n);
for(i = ;i <= n;i++)
{
for(j = ;j <= n / i;j++)
{
if(i * j > n)
break;
sum[i * j] += i;
}
}
}
void dp()
{
int i;
for(i = n;i >= ;i--) //因为大数字一定是小数字的后代
{
if(sum[i] < i) //sum[i]是i的父亲节点
{
if(d1[i] + > d1[sum[i]])//修改sum[i]这点的最大值
{
d2[sum[i]] = d1[sum[i]];
d1[sum[i]] = d1[i] + ;
}
else if(d1[i] + >d2[sum[i]])
{
d2[sum[i]] = d1[i] + ;
}
}
}
}
int main()
{
int i,ans = ;
ready();
dp();
for(i = ;i <= n;i++) //遍历所有的节点，找最大值+次大值的最大值
{
if(d1[i] + d2[i] > ans)
ans = d1[i] + d2[i];
}
printf("%d",ans);
return ;
}