14501: 퇴사

[minsoo0715]

14501: 퇴사

소스 코드

아이디어

$A_n$을 n일에 상담을 진행했을 때의 최댓값으로 정의했다.
따라서 $A_i$은 $i + P_i\leq k \leq N$에서 최대값을 갖는 값을 $A_k$라고 할 때 이에 $P_K$를 더한 것과 같다.

$$A_i = A_k + P_k \; (A_k는 \;\; i + P_i\leq k \leq N 에서의\;최댓값)$$
또한 $i + T_i > N$ 일 때 $A_i = P_k$ 이다.

$$A_i = P_i \; (i + T_i > N)$$

구현

재귀를 이용해 top-down 방식으로 구현, 편의를 위해서 $A_0$에 최대값 저장. 0일차($T_0 = 0$)는 무조건 포함시킨다고 생각하면 될 듯

int solve(int k = 0) {
    if(k + t[k] > n+1) { // 범위를 넘어가면 0
        return 0;
    }
    if(dp[k] != -1) {
        return dp[k];
    }

    int &ref = dp[k] = 0;

    for(int i = k + t[k]; i<=n; ++i) {  // k + t[k] <=  i <= n 내에서의 최대값
        ref = std::max(solve(i), ref);
    }

    return ref += p[k];
}

std::cout << solve(0);