読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミング

【AOJ 1167】Pollock's conjecture

問題

Pollock's conjecture | Aizu Online Judge

方針

  • 動的計画法を使う.
  •  { dp[n]:=} nを表現するのに必要な正四面体の数の最小値 としたとき,  {dp[n]} {dp[n] = min(dp[n-1], dp[n-4], dp[n-1-], \cdots , dp[n-n以下最大の正四面体数]) + 1}として求めることができる.
  • 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;    
  }
}

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