hdu 4112 Break the Chocolate

제목 링크: hdu 4112 Break the Chocolate
제목 대의: N∗M∗K의 초콜릿을 정하고, 지금은 두 가지 방식으로 단위 크기로 전환한다. 하나는 손으로 한 번 쪼개서 두 개를 두 조각으로 나눈다.
칼로 자르는 것으로 같은 방향에서 두 조각을 겹쳐 자르는 것이다.
문제풀이 방향: 첫 번째는 N∗M∗K-1이고, 두 번째는 dp[i]를 미리 처리하여 이 방향의 길이가 i라고 할 때 몇 칼을 잘라야 한다는 뜻이다.
dp[N]+dp[M]+dp[K].

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 2005;

ll N, M, K, dp[maxn];

int main () {
    int cas;
    scanf("%d", &cas);
    dp[1] = 0;
    for (int i = 2; i < maxn; i++)
        dp[i] = dp[(i+1)/2] + 1;

    for (int kcas = 1; kcas <= cas; kcas++) {
        scanf("%I64d%I64d%I64d", &N, &M, &K);
        printf("Case #%d: %I64d %I64d
", kcas, N * M * K - 1, dp[N] + dp[M] + dp[K]);
    }
    return 0;
}