SRM205 Div2 hard HexagonalSums

問題概要：
n (1 <= n <= 1000000)が与えられる
n を hexagonal number の和で表した時に必要な最小の hexagonal number の数を返せ

解法：
DPで解いた
最初に n 以下の hexagonal number をベクターとかに入れておく
dp[n] := n を作るために必要な最小の hexagonal number の数
として

for i 0..(n 以下の hexagonal number の数)
  for j (i 番目の hexagonal number)..n
    dp[j] = min(dp[j],
                dp[j-(i 番目の hexagonal number)]+1)

とした
あれです、個数制限なしのナップザック問題です

コード；

int mincost[MAX+1];

class HexagonalSums {
	public:

  void createHex(vector<int> &hexa)
  {
    int value = 1;
    int diff = -1;
    while(value <= MAX)
      {
	hexa.push_back(value);
	value += (diff == -1?(diff=5):(diff=diff+4));
      }
  }

  int minLength(int N) {
    vector<int> hexa;
    createHex(hexa);  
    int n = hexa.size();
    N=N;
    rep(i,MAX+1)mincost[i] = INF;
    rep(i,n)mincost[hexa[i]] = 1;

    rep(i,n)
      for(int j=hexa[i];j<=N;j++)
	mincost[j] = min(mincost[j],
			 mincost[j-hexa[i]]+1);

    assert(mincost[N] != INF);
    return mincost[N];
  }
};