leetcode-go/poj/1190.birthday-cake/main.cc

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10000;
const int M = 20;
const int INF = 1 << 30;

int n, m, min_area = INF;

int min_v[M + 1]; // Min v required for i layers cake
int min_a[M + 1]; // Min side area required

int maxv_for_lrh(int l, int r, int h) { // Max v for given l, r and h
  int v = 0;
  for (int i = 0; i < l; i++) v += (r - i) * (r - i) * (h - i);
  return v;
}

void dfs(int l, int v, int area, int r, int h) {
  if (l == 0) {
    if (v) return;
    min_area = min(min_area, area);
    return;
  }
  if (v <= 0) return;
  if (v < min_v[l]) return;
  if (min_area <= area + min_a[l]) return;
  if (r < l || h < l) return;
  if (maxv_for_lrh(l, r, h) < v) return;
  for (int nr = r; l <= nr; nr--) {
    if (l == m) area = nr * nr;  // The area of bottom
    for (int nh = h; l <= nh; nh--)
      dfs(l - 1, v - nr * nr * nh, area + 2 * nr * nh, nr - 1, nh - 1);
  }
}

int main() {
  scanf("%d %d", &n, &m);
  min_v[0] = 0;
  min_a[0] = 0;
  for (int i = 1; i <= m; i++) {
    min_v[i] = min_v[i - 1] + i * i * i;
    min_a[i] = min_a[i - 1] + 2 * i * i;
  }
  if (min_v[m] <= n) { // Max h and r for bottom layer
    int max_h = (n - min_v[m - 1]) / (m * m) + 1;
    int max_r = sqrt(double(n - min_v[m - 1]) / m) + 1;
    dfs(m, n, 0, max_r, max_h);
  }
  if (min_area == INF)
    printf("0\n");
  else
    printf("%d\n", min_area);
  return 0;
}