[每日一题] [NC20272] 生日快乐

题目大意：有N(<=10)个人，需要把X*Y的蛋糕切成N等份，每次只能横／竖切一刀。求最大的长宽比的最小值。其中矩形的长宽比为长边与短边的比值。

https://ac.nowcoder.com/acm/problem/20272

数据比较小，N只有10，直接用了个dfs就解决了。考虑XY的蛋糕切成N份，子问题是max((X1/N)Y切成1份，(X(N-1)/N)*Y切成N-1份)等等的最小值。

不是很确定的复杂度分析:
T(n)=4(T(1)+...+T(n-1))
=>T(n)=T(n-1)+4T(n-1)=5*T(n-1)=>T(n)=5^n

int X, Y;
int N;

double dfs(double X, double Y, int N) {
  if (N == 1) {
    return max(X, Y) / min(X, Y);
  }
  // Split X.
  double ans = 10000000;
  for (int l = 1; l < N; ++l) {
    ans = min(ans, max(dfs(X / N * l, Y, l), dfs(X / N * (N - l), Y, N - l)));
  }
  for (int l = 1; l < N; ++l) {
    ans = min(ans, max(dfs(X, Y / N * l, l), dfs(X, Y / N * (N - l), N - l)));
  }
  return ans;
}

int main(int argc, char* argv[]) {
  read(X, Y, N);
  double ans = dfs(X, Y, N);
  printf("%.6lf\n", ans);
  return 0;
}