[SCOI2009]生日快乐

题意：
将一块x*y的蛋糕切n-1刀分成n块面积相同的小蛋糕，每次切只能平行于边将一块切成二块。求N块蛋糕的长边与短边的比值的最大值最小为多少？

思路：
我们发现n<=10,而且每次切只能平行于边将一块切成二块，而且每一块面积相同，所以我们可以用dfs枚举每一种切法。
平行于y边切：可以切成(i * x/n) * y和((n-i) * x/n) * y两块（0<i<n，x/n表示将x分为n份，你只能切这份额的倍数，否则会导致最终无法切成面积相等的n块）
平行于x边切：可以切成(i * y/n) * x和((n-i) * y/n) * x两块

代码：

#include <bits/stdc++.h>
#define inf 1000000007
#define eps 0.000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

double dfs(double x,double y,double n)
{
    if(n==1)
    {
        return max(x,y)/min(x,y);
    }
    double z=inf;
    for(int i=1;i<n;i++)
    {
         z=min(z,min(max(dfs(i*x*1.0/n,y,i),dfs((n-i)*x*1.0/n,y,n-i)),max(dfs(x,i*y*1.0/n,i),dfs(x,(n-i)*y*1.0/n,n-i))));
    }
    return z;
}

int main()
{
    double x, y, n;
    scanf("%lf%lf%lf",&x,&y,&n);
    double z=dfs(x,y,n);
    printf("%.6f",z);
    return 0;
}