题意:如果一个数x的 约数和y (不包括x本身)比它本身小，那么x可以变成y,y也可以变成x.例如4可以变为3,7可以变为1.限定所有数字变换在不超过(n(n<=50000))的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数.
分析:先预处理出每个数i的约数和sum[i],如果(sum[i]<i),则在它们之间连边,为了方便我们建一条由sum[i]指向i的有向边,长度显然为1.这样一定会构成一棵以1为根树.于是题目转换为了求树的最长链问题,可以用树形DP求解.
但因为本题比较特殊,我们已经知道了大数字一定为小数字的后代,所以我们直接从后往前枚举,不断更新最大值和次大值.
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int N=50005;
int sum[N],d1[N],d2[N];
int main(){
int n=read();
for(int i=1;i<=n;i++)
for(int j=2;i*j<=n;j++)
sum[i*j]+=i;//i是i*j的约数,求i*j的约数和
for(int i=n;i>=1;i--){
if(sum[i]<i){
if(d1[i]+1>d1[sum[i]]){
d2[sum[i]]=d1[sum[i]];//先要更新次大值
d1[sum[i]]=d1[i]+1;//更新最大值
}
else if(d1[i]+1>d2[sum[i]])
d2[sum[i]]=d1[i]+1;
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,d1[i]+d2[i]);
printf("%d
",ans);
return 0;
}