【AOJ 1167】Pollock's conjecture

問題

Pollock's conjecture | Aizu Online Judge

方針

• 動的計画法を使う.
• nを表現するのに必要な正四面体の数の最小値 としたとき, はとして求めることができる.
• 1から順番にもとめておき, 入力したnを添え字にしてテーブルを出力する.

コード

#include<iostream>
#include<vector>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define INF 1e9
#define pb push_back
 
using namespace std;
 
typedef long long ll;
 
#define MAX 1000001
 
signed main(){
  int n;
  int ans_odd[MAX], ans[MAX];
  vector<int> v1, v2;
 
  rep(i, 301){
    int hoge = i * (i+1) * (i+2) / 6;
    v1.pb(hoge);
    if(hoge%2 == 1) v2.pb(hoge);
  }
 
  rep(i, 1000001){
    ans[i] = ans_odd[i] = INF;
  }
   
  ans[0] = ans_odd[0] = 0;
   
  REP(i, 1, MAX){
    REP(j, 1, v1.size()){
      if(v1[j] > i) break;      
      ans[i] = min(ans[i], ans[i - v1[j]]+1);
    }
  }
 
  REP(i, 1, MAX){
    ans_odd[i] = i;
    REP(j, 1, v2.size()){
      if(v2[j] > i) break;
      ans_odd[i] = min(ans_odd[i], ans_odd[i - v2[j]]+1);
    }
  }
  
  while(cin >> n, n){
    cout << ans[n] << " " << ans_odd[n] << endl;    
  }
}

頭悪すぎて書くのにすごい時間がかかった…