1167. Pollock's conjecture

問題

n番目の正四面体数は、n*(n+1)*(n+2)/6に等しい。
Nが与えられたとき、そのNを複数の正四面体数の和で表現したい。(同じ正四面体数を何度も使ってよい)
組み合わせる正四面体数が最小になるようにNを表現したときの組み合わせ数を求めよ。
また、組み合わせる正四面体数が奇数のみ許される場合でも同様に求めよ。

1<=N<10^6

考え方

まず、どちらの場合でも1番目の正四面体数は1なので、これを使えばすべての数が作れる。

dp[i]:=数字iを正四面体数の和で表す最小組み合わせ数
とすると、v[j]をj番目の正四面体数とし、dp[i]=min(dp[i], dp[i-v[j]]+1)で更新できる。
i-v[j]は1〜i-1までの範囲で見る必要があるが、全部合わせても1.33*10^8回程度なので、制限時間には間に合う。

dpを求めておけば、各クエリはO(1)で求められる。
奇数のみ許される場合は、v[j]が奇数のときのみ更新する別配列を用意しておけばよい。