信息学奥赛一本通提高篇 1577：【例 3】数字转换树型动态规划

长春高老师编程

538人浏览 · 2024-12-17 15:19:08

长春高老师编程 · 2024-12-17 15:19:08 发布

1577：【例 3】数字转换

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

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

【输入】

输入一个正整数 n。

【输出】

输出不断进行数字变换且不出现重复数字的最多变换步数。

【输入样例】

【输出样例】

【提示】

样例说明

一种方案为 4→3→1→7。

数据范围与提示：

对于 100% 的数据，1≤n≤50000。

【解析】

由题意可知，若x的约数和y比x小，那么两个数之间就有了一条边。

那么所有可以变化的数会组成一个以1为根的树。且父节点比子节点小；

在这个树上找到一条最长的链即为答案；

详见代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int fa[50005];//fa[i]表示i的父节点
int mx1[50005], mx2[50005]; //最长子树链和次长子树链
int ans = 0;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) { //计算每个数的约数和
        for(int j = 2; i * j <= n; j++) {
            fa[i * j] += i;
        }
    }
    for(int i = n; i >= 1; i--) { //从子节点枚举到根节点
        if (fa[i] < i) { //如果有父节点
            //比父节点最大值大，最大值替换次大值，替换最大值
            if (mx1[i] + 1 > mx1[fa[i]]) {
                mx2[fa[i]] = mx1[fa[i]];
                mx1[fa[i]] = mx1[i] + 1;
            } else if (mx1[i] + 1 > mx2[fa[i]]) { //比次大值大，替换次大值
                mx2[fa[i]] = mx1[i] + 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) { //遍历所有节点
        ans = max(ans, mx1[i] + mx2[i]); //取最长链
    }
    cout << ans;
    return 0;
}