AOJ 1167: Pollock's conjecture
問題
Pollock's conjecture | Aizu Online Judge
- 与えられた数を正四面体数(n番目の正四面体数はである)の和で表すときに最小でいくつの数が必要か
- また奇数の正四面体数のみの和で表すときはどうか
方針
動的計画法を使う
dp[n]
はnを表すのに必要な最小の正四面体数の個数を表す行列とする。
初期条件はdp[0]=0
。
それぞれの正四面体数i
について
i
を使うならdp[n]=dp[n-i]+1
が最小の個数i
を使わないなら現在dp[n]
に入っている数が最小の個数
であるので、dp[n]=min(dp[n-i]+1, dp[n])
として行列を更新していく。
奇数の場合も同様。
正四面体数はあらかじめ200番目(=1353400)まで求めておき、奇数番目だけ抜き出して他の行列に入れておいた。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) const int size = 200; const int limit = 1000001; int dp[limit], dp_odd[limit]; int tetra[size], odd[size]; int main(void){ int size_odd = 0; for(int i=1; i<size+1; ++i) { ll t = i*(i+1)*(i+2)/6; tetra[i-1] = t; if(t%2==1) {odd[size_odd]=t; size_odd++;} } int inf = numeric_limits<int>::max(); rep(i, limit) dp[i] = dp_odd[i] = inf; dp[0] = 0; dp_odd[0] = 0; rep(i, size) { for(int j=tetra[i]; j<limit; ++j) dp[j] = min(dp[j-tetra[i]]+1, dp[j]); } rep(i, size_odd) { for(int j=odd[i]; j<limit; ++j) dp_odd[j] = min(dp_odd[j-odd[i]]+1, dp_odd[j]); } int n; while(cin >> n && n) { cout << dp[n] << " "; cout << dp_odd[n] << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1896259#2
反省
- dpを思いつかずに、再帰でやったらTLEした。AOJが20 sまで待ってくれることにびっくりした