[BAE/<JOON> 문제풀이] 3943. 헤일스톤 수열 (DP.040)

https://www.acmicpc.net/problem/3943

3943번: 헤일스톤 수열

파일 합치기 풀다가 시간 딸림.

 

근데 이 문제도 오래걸림

 

앞으로 iostream 걸러야겠다.

 

무조건 cstdio쓴다. cin.tie(NULL), ios_base::sync어쩌구 쓰고 푸는데 안되서

 

혹시나하고 scanf printf쓰니까 바로 맞는다

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>

using namespace std;
vector<int> dp;

unsigned long long r(unsigned long long n, unsigned long long max) {
    if (n == 1) return max;
    if (n < 10000000) {
        if (dp[n] != -1) return max > dp[n] ? max : dp[n];
    }
    if (n % 2 == 0) {
        unsigned long long res = r(n / 2, max);        
        return max > res ? max : res;
    }
    else {        
        unsigned long long res = r(n * 3 + 1, max > (n * 3 + 1) ? max : (n * 3 + 1));        
        return max > res ? max : res;
    }
}

int main()
{    
    int tc;
    scanf("%d", &tc);
    dp.assign(10000001, -1);
    for (int t = 1; t <= tc; t++) {
        int n;
        scanf("%d", &n);
        if (dp[n] != -1) {
            printf("%d\n", dp[n]);
            continue;
        }         

        dp[n] = r(n, n);
        printf("%d\n", dp[n]);
    }
    return 0;
}