本文共 3782 字，大约阅读时间需要 12 分钟。

DP/数论 - 树形DP - 数字转换

如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。

例如，4 可以变为 3，1 可以变为 7。

限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输出格式

数据范围

输入样例：7输出样例：3

样例解释

分析：

$$\begin{gathered} 由题意知道，每个数字均能够在一些数字之间进行转化，要求转化的最多次数。 \\ 抽象地，就是在一颗树中，求两个状态之间的最大距离，也就是树的最长路径。 \end{gathered}$$

$$\begin{gathered} 对每个正整数n，首先分解出n的所有约数，对这些约数求和为sum[n]， \\ 若sum[n]<n，则二者之间能够相互转化，就在n与sum[n]之间建立一条无向边。 \end{gathered}$$

$最后在树中求一遍最长路径即可。$———《》。

$$\begin{gathered} sum数组的求取： \\ 最暴力的方式是对每个n以O(\sqrt{n})暴力枚举所有约数并求和，总的时间复杂度是O(n\sqrt{n})，能过，但不够优秀。 \\ 好一点的方式是反过来，对每个整数i，将i累加到i的所有倍数中去。 \\ 类似于线性筛的过程，对每个整数i，将i累加到i\times j上去，(j=2,3,...,n/i)。时间复杂度O(nlogn)。 \end{gathered}$$

另外： $因为本题是有向图，为了确保得到整个图的最长路径，可以遍历从每个未被访问过的节点进入dfs。$

但是：$$\begin{gathered} 仔细想一想似乎并不需要，从从每个节点进入搜索。 \\ 只需要从1进入搜索一遍就可以了。 \end{gathered}$$

$$\begin{gathered} 原因是：1能够到达所有质数。 \\ ①、若某个数u的约数之和是质数sum[u]，那么必有一条路径1->sum[u]->u。 \\ ②、若某个数u的约数之和是合数sum[u]，因为sum[u]<u， \\ 那么必有一条路径u->sum[u]->sum[sum[u]]->...质数P->1。也就是从1到u的一条路径。 \end{gathered}$$

$测试下来从1进入搜索就能够得到最长路径。$

$$\begin{gathered} 若严格证明要说明一个问题：1所在的连通块中的最长路径就是整个图的最长路径。 \\ 若某个数不在1所在的连通块中，说明这个数在转移的过程中，某个中间状态的约数之和大于其本身。 \\ 也就是要说明那些约数之和大于本身的数，这些数构成的连通块中的最长路径要小于1所在的连通块的最长路径。 \end{gathered}$$

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int N=50010;int e[N],ne[N],h[N],idx;int n,sum[N],ans;bool st[N];void add(int a,int b){
       e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int dfs(int u){
       st[u]=true;    int d1=0,d2=0;    for(int i=h[u];~i;i=ne[i])    {
           int j=e[i];        if(!st[j])        {
               int d=dfs(j)+1;            if(d>=d1) d2=d1,d1=d;            else if(d>d2) d2=d;        }    }    ans=max(ans,d1+d2);    return d1;}int main(){
       memset(h,-1,sizeof h);        scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=2;j<=n/i;j++)            sum[i*j]+=i;        for(int i=2;i<=n;i++)        if(sum[i]
     
    
   

转载地址：http://epor.baihongyu.com/