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

Problem C ポロック予想

動的計画法。和がnになる正四面体数の最小個数をA_nとし、n以下の正四面体数の集合をT(n)とすると、
A_n = min_t∈T(n)(A_n-t+1)。
奇数のみの場合も同様。

#include <iostream>

using namespace std;

int main()
{
    const int N = 1000000;

    static int A[N];    //  正四面体数の個数
    static int B[N];    //  奇数の正四面体数の個数
    A[0] = B[0] = 0;

    for ( int i=1; i<N; i++ )
    {
        A[i] = B[i] = i;

        for ( int j=1; ; j++ )
        {
            int t = j*(j+1)*(j+2)/6;
            if ( t > i )
                break;

            A[i] = min( A[i], A[i-t]+1 );
            if ( t%2 == 1 )
                B[i] = min( B[i], B[i-t]+1 );
        }
    }

    while ( true )
    {
        int n;  cin >> n;
        if ( n == 0 )
            break;

        cout << A[n] << " " << B[n] << endl;
    }
}