Question

帮忙分析一个c++试题，算法方面的。程序有了，特别是solve() 函数，理解不了，帮忙分析一下吧

问题描述
如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。

输入数据
输入一个正整数n。

输出数据
输出最少需要花费的时间。

样例输入
7

样例输出
3

样例说明
一种方案为：4→3→1→7。

时间限制
各测试点1秒

内存限制
你的程序将被分配32MB的运行空间

数据范围
n<=50 000。

#include <fstream>
using namespace std;
ifstream fin("44.in") ;
ofstream fout("44.out");
long f1[50000],f2[50000];
long sum[50000];
long n;
void init()
{
for(long i=1;i<=n;i+=1)
{
long t;
t=i*2;
while(t<=n)
{
sum[t]+=i;
t+=i;

}

}
}

void solve()
{
for(int i=n;i>=1;i-=1)
{
long t=sum[i];
if(t>=i) continue;
if(f1[i]+1>f1[t])
{
f2[t]=f1[t];
f1[t]=f1[i]+1;

}
else if(f1[i]+1>f2[t])
{
f2[t]=f1[i]+1;
}

}
}
void print()
{
long max=0;

for(long i=1;i<=n;i++)
{
if(f1[i]+f2[i]>max)
{
max=f1[i]+f2[i];
}

}
fout<<max;
}

int main()
{
fin>>n;
init();
solve();
print();
}
f1 f2这两个数组是做什么的。具体怎么回事呢

Answer 1

首先我们知道一条可行方案必定是一条链而不可能是一个环
那么所有可进行变化的数之间连边就是一棵树，我们要求这棵树里最长链.
那么就是一个树形dp，每个点记录以他为一端的最长链和次长链。
最后枚举每个点，看经过哪个点的连最长即为答案.
f1为最长链，f2为次长链

追问

if(f1[i]+1>f1[t])
{
f2[t]=f1[t];
f1[t]=f1[i]+1;
}
else if(f1[i]+1>f2[t])
{
f2[t]=f1[i]+1;
}
这一句怎么解析？

追答

t 是 i 的 父亲
if f1[i]+1>f1[t] 即是说如果用i来更新t的最长链和次长链时发现这个结果比最长链更优，就把原来的最长链赋值给次长链，最长链为新的值，否则如果新的值大于次长链，则把新的值赋给次长链

追问

max=f1[i]+f2[i];
这是不是把最长链和次长链加起来了？ 是什么意思。。麻烦你了。我第一次接触这个东西。可以多给你一些分

追答

不好意思，我没有说清楚，这里的最长链和次长链均是指以该点为一端的最长链和次长链，因此最长链和次长链接起来就是以该点为根的子树里，经过这个点的最长的一条链.