现有一块长为 X X ，宽为 Y Y 的蛋糕，切 N−1 N - 1 刀，分成 N N 块，在保证每块蛋糕面积相等的前提下使得 N N 块切好的蛋糕长边比短边的最大值最小，求这个最小值。

题解

乍一看感觉除了搜好像没有什么更好的做法，但是想了想感觉 X,Y X, Y 的范围看起来让人发虚。。

于是就咸鱼的看了题解。。才注意到 N≤10 N \leq 10 这个可爱的条件。

首先，对于需要被等分成 N N 块的长为 X X ，宽为 Y Y 的蛋糕，若横切，则分成的两块的宽度必须为 ⌊YN⌋ \lfloor \frac Y N \rfloor 的整数倍，否则一定无法满足等分，纵切情况类似。

由于 N N 很小，可以直接暴搜，设当前状态为面对一块长为 x x ，宽为 y y ，需要被分成 d d 块的蛋糕，分横切纵切枚举分成的两块的长或宽，搜出来最大的长宽比更新答案即可。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
double dfs(double x, double y, int d) {
    double res = 100000.0;
    if (d == 1) {
        if (x < y) std::swap(x, y);
        return x / y;
    }
    double xx = x / d;
    for (int i = 1; i <= d / 2; i++) {
        double temp = std::max(dfs(xx * i, y, i), dfs(x - xx * i, y, d - i));
     	res = std::min(res, temp);
    }
    double yy = y / d;
    for (int i = 1; i <= d / 2; i++) {
        double temp = std::max(dfs(x, yy * i, i), dfs(x, y - yy * i, d - i));
        res = std::min(res, temp);
    }
    return res;
}
int main() {
    int x, y, n;
    scanf("%d %d %d", &x, &y, &n);
    printf("%.6lf\n", dfs(x, y, n));
    return 0;
}