ACM-ICPC 2010年 国内予選 問題C ポロック予想

問題C:ポロック予想(Inputの10^6が106に見えるので注意)

dp[n] = 「正整数nを表すために必要な正四面体数の個数の最小」とする。この時、dp[n] = min(dp[n-1], dp[n-4], dp[n-10], ... , dp[n - (n以下である、正四面体数の最大)]) + 1となる。

奇数の場合も同様に考える。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int tri[182];
int squ[182];//181*182*183/6 = 1004731 > 10^6

#define MAX 1000000
int dp[MAX], dp_odd[MAX];

int n;

int main()
{
    tri[0] = squ[0] = 0;
    for (int i = 1; i < 182; i++)
        tri[i] = tri[i-1] + i,
        squ[i] = squ[i-1] + tri[i];

    dp[0] = dp_odd[0] = 0;
    for (int i = 1; i < MAX; i++) {
        //少なくともsqu[1]=1をi個だけ用いて表せる。
        dp[i] = dp_odd[i] = i;

        for (int j = 1;; j++) {
            int t = squ[j];
            if (t > i)    break;

            dp[i] = min(dp[i], dp[i-t]+1);
            if (t&1)
                dp_odd[i] = min(dp_odd[i], dp_odd[i-t]+1);
        }
    }

    while (cin >> n, n)
        printf("%d %d\n", dp[n], dp_odd[n]);
    return 0;
}