UVa1158

UVa1158

DPする。

#include<iostream>
#include <algorithm>

using namespace std;

typedef long long int lli;

const lli inf = 1LL << 60;
const lli N = 400000 + 1;
lli dp[N];

const lli S = 180;
lli sum[S];

int main(void)
{
  sum[0] = 0;
  for (lli i = 1; i < S; ++i) {
    sum[i] += sum[i - 1] + i * i;
  }

  fill(dp, dp + N, inf);
  dp[0] = 0;
  
  for (lli i = 0; i < N; ++i) {

    for (lli j = 0; j < S; ++j) {
      if (i + sum[j] < N) ; else break;
      dp[i + sum[j]] = min(dp[i + sum[j]], dp[i] + 1);
    }

    for (lli j = 0; j * j * j < N; ++j) {
      lli k = j * j * j;
      if (i + k < N) ; else break;
      dp[i + k] = min(dp[i + k], dp[i] + 1);
    }
  }

  int n;
  while (cin >> n) {
    if (n == -1) break;
    cout << dp[n] << endl;
  }

  return 0;
}