提交地址：http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1709
问题描述
如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。
输入数据 输入一个正整数n。
输出数据 输出最少需要花费的时间。 （这里原题应该打错了，应该是输出最大转换步数）
样例说明 一种方案为：4→3→1→7。
时间限制 各测试点1秒
内存限制 你的程序将被分配32MB的运行空间
数据范围 n<=50 000。
如果x和y可以互相转化，就连接一条无向边，最后得到的图其实是一个森林，每棵树都是无根树，其实就是要求，整个森林中两个连通的点的最远距离（这里边权都是1），和在无根树中求两点最远距离是一样的，不过这题的特殊性，可以更方便点
对于任意一条边，必有x<y，在树中，x就应该为y的双亲（因为y的约数和是唯一的，但x可能是很多个数的约数和，这正好对应树的关系，双亲唯一，孩子不定）。而dp思想照样是找出每个节点到叶子的最大值m1和次大值m2，再两者相加的dp[rt]，而整个树中的最大值，就是扫描全部节点，找到最大的dp[rt]
由于这题，每个节点的双亲是可以记录下来的，所以dp的时候不用递归，而写成递推式，直接从叶往上递推，为什么不能从根往下递推呢，这很容易理解，想想我们是怎么计算m1和m2的
还有一个重要的时候就是怎么找出约数和，数据比较大，应该尽量避免多余的判断，用筛法求约数和则是一个不错的方法
#include <cstdio> #include <cstring> #define N 50000 #define max(a,b) ((a)>(b)?(a):(b))int n; int sum[N]; long long dp[N][2];void make() {for(int i=1; i<=n; i++) sum[i]=1;for(int i=2; i<=n/2; i++) //约数for(int j=2*i; j<=n; j+=i)sum[j]+=i;// for(int i=1; i<=n; i++) printf("%d ",sum[i]); printf("\n"); }void solve() {memset(dp,0,sizeof(dp));for(int i=n; i>=1; i--) if(sum[i] < i) //有合法的约数和 {// dp[i] ---> dp[sum[i]]if(dp[i][1]+1 > dp[sum[i]][1]){dp[sum[i]][0] = dp[sum[i]][1];dp[sum[i]][1] = dp[i][1]+1;}else if(dp[i][1]+1 > dp[sum[i]][0])dp[sum[i]][0] = dp[i][1]+1;}long long res=0;for(int i=1; i<=n; i++) res=max((dp[i][0]+dp[i][1]),res);printf("%lld\n",res); }int main() {while(scanf("%d",&n)!=EOF){make(); //筛法构造约数和 solve();}return 0; }
