链接：https://ac.nowcoder.com/acm/contest/23156/1026
来源：牛客网

题目描述

windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy ，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。
windy主刀，每一切只能平行于一块蛋糕 的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 N 块蛋糕，windy必须切 N-1 次。
为了使得每块蛋糕看起来漂亮，我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？

输入描述: 

包含三个整数，X Y N。
1 ≤ X,Y ≤ 10000 ； 1 ≤ N ≤ 10

输出描述: 

包含一个浮点数，保留6位小数。

思路

P.S:题目中说了，每一切只能平行于一块蛋糕 的一边（任意一边），并且必须把这块蛋糕切成两块，所以不要想成那种2刀切4块，那种切法第2刀是对第1刀切成的2块蛋糕同时切分，不满足题意
先看数据范围，发现n<=10，可以直接用搜索来做，这里选用DFS
设蛋糕的长为y，宽为x，一共切了n刀
首先，题目要求了每一块切出来的蛋糕必须等体积，这就意味着，每一次切出来的蛋糕，如果是按横着切，长度一定是x/n的倍数（这里的证明很简单，可以用设变量计算矩形的面积得出，最后一定会得到x=k*a(k为常数)）
如果是按竖着切，长度一定是y/n的倍数（这里的证明同上）
至于从哪里开始切，又要切到哪里的范围限定：对于一个矩形来说，它从最左边(即i=1)开始切，一直切到中间或者是靠近中间的位置（即i/2），和从最右边开始切，一直切到中间或者是靠近中间的位置，是等价的。（对称性）
所以范围可以限定到1~(n/2)之间（不限定的话，会MLE）
最后，答案要求长与宽的比值的最大值最小。
对于求最大比值的最小值好办，设答案为ans，直接ans=min(ans,min(比值));即可
对于求最大比值
首先看n=1时，表明已经切完了（因为一共要切n-1刀），此时直接return比值最大值，即max(x,y)/min(x,y);
当n!=1时，表明还要继续切
设此时横着切的最大长宽比值为h，竖着切的最大长宽比值为s，可以得到递归的式子为h=max(DFS(宽度*（前面共i块），长度（不变），块数i)，DFS(宽度*（后面共n-i块），长度（不变），块数(n-i)));
s同理
这样DFS的基本结构就很清楚的写出来了
这题总体来说难度不算高，但是需要正确的表达DFS的递推式才能得到正解，感觉多做做这种题目对于自己的思维训练和递推式训练还是比较有帮助的awa

代码如下
#include<bits/stdc++.h>
using namespace std;
int n;
double x,y;
double DFS(double x,double y,int n){
    if(n==1){
        return max(x,y)/min(x,y);
    }
    double ans=100000000,a=x/n,b=y/n; //注意初始化
    for(int i=1;i<=(n/2);i++){
        double h=max(DFS(a*i,y,i),DFS(x-a*i,y,n-i));
        double s=max(DFS(x,b*i,i),DFS(x,y-b*i,n-i));
        ans=min(ans,min(h,s));
    }
    return ans;
}
int main(){
    scanf("%lf%lf%d",&x,&y,&n);
    printf("%.6lf\n",DFS(x,y,n)); //注意保留6位小数
    return 0;
}