ACM-ICPC 2010国内予選 C. ポロック予想

C. ポロック予想

解法

• 動的計画法
  • Nを何個の正四面体数で表せるかは，1〜N-1の答えを使って求められる
  • ansA[i]を「iを表すために必要な最小の正四面体数の数」とする
  • 正四面体数1, 4, 10, 20, …に対し，
    • ansA[N] = min(ansA[N-1], ans[N-4], ans[N-10], …) + 1
  • 何故か求める奇数だけを使った場合も同様
• 100万くらいなら答えを全部持っておけるので、あらかじめ全部計算してしまう

#include <iostream>

using namespace std;

int main(){
	int N;
	int tri[200];
	static int ansA[1000000], ansB[1000000];
	for(int i=0;i<200;i++) tri[i] = i*(i+1)*(i+2)/6;
	ansA[0] = ansB[0] = 0;
	for(int i=1;i<1000000;i++){
		ansA[i] = ansB[i] = i;
		for(int j=0;i-tri[j]>=0;j++){
			ansA[i] = min(ansA[i], ansA[i-tri[j]]+1);
			if(tri[j]%2==1)
				ansB[i] = min(ansB[i], ansB[i-tri[j]]+1);
		}
	}
	while(cin >> N, N)
		cout << ansA[N] << " " << ansB[N] << endl;
}