分析

一个数，奇数就乘三加一，偶数减半，一定可以通过有限步到达一。在该过程中都有一个最高峰。
现在给一个数n，问1到n所有变化过程中的最高峰是多高？

乍一看，不是O(logn)，我以为那dfs一定是O(n)以上的复杂度。

所以，当外层循环n为100万，只能用记忆化的方法。于是，先用线性哈希数组flag[1e6+10]记忆最高峰，不行，最大数可以八位甚至更多，又改为unourdered_map<int,int> falg;还是不行，存储数据太多，查找超时。

后来一看题解，可以暴力搜索……

突然意识到，dfs(n)的递归层数可能和n无关，或者说，没有线性关系。实验发现，最大递归层数总是不超过600{在所给数据范围下}，所以，两层以n为参数的循环套起来居然是O(600n)也就是O(n)，好吧！

实际上，平均起来，甚至不到200n。

C++ 代码

#include<iostream>
using namespace std;

typedef long long LL;
LL get(LL x)
{
    LL res = x;
    while(x != 1)
    {
        x&1 ? x = 3 * x + 1 : x >>= 1;
        res=max(res,x);
    }
    return res;
}


int main(){
    int n;cin>>n;
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res,get(i));
    }
    cout<<res<<endl;
    return 0;
}

改进一下，只考虑奇数

#include<iostream>
using namespace std;

typedef long long LL;

int n;

LL get(LL x)
{
    LL res = x;
    while(x != 1)
    {
        x&1 ? x = 3 * x + 1 : x >>= 1;
        res=max(res,x);
    }
    return res;
}

int main()
{
    cin >> n;
    LL res = 1;
    if(n > 2)
    {
        LL i = n>>1; //从n的一半开始枚举
        for(i=(i&1)? i:i+1; i <= n; i += 2)
            res = max(res,get(i));
    }else res=n;

    cout << res;
    return 0;
}