Project Euler Problem 14-Longest Collatz sequence

记忆化搜索来一发。没想到中间会爆int

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000000;

int dp[MAXN];

int dfs(long long num)

{

    if(num <= MAXN && dp[num]) return dp[num];

    if(num == 1) return (dp[num] = 1);

    if(num&1)

    {

        if(num <= MAXN) return (dp[num] = dfs(num*3+1)+1);

        else return dfs(num*3+1)+1;

    }

    else

    {

        if(num <= MAXN) return (dp[num] = dfs(num/2)+1);

        else return dfs(num/2)+1;

    }

}

int main()

{

    int len = 0,res,maxn = 0;

    for(int i = 1; i <= MAXN; ++i)

    {

        len = dfs(i);

        if(len > maxn)

        {

            maxn = len;

            res = i;

        }

    }

    printf("%d\n",res);

    return 0;

}

巴特西

Project Euler Problem 14-Longest Collatz sequence

最新文章

热门文章