Description
windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy
，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕
的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 N 块蛋糕，windy必须切 N-1 次。为了使得
每块蛋糕看起来漂亮，我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？
Input
包含三个整数，X Y N。1 <= X,Y <= 10000 ； 1 <= N <= 10
Output
包含一个浮点数，保留6位小数。
Sample Input
Sample Output
1.800000
题解
我们可以发现，$n$非常小。虽然“最大值最小”看上去像是二分，但是$n$那么小可以搜索。
那么，我们令$dfs(x,y,n)$表示答案，那么第一步切法有：
$$dfs(x,y,n)=minleft{maxleft(dfs(x*i/n,y,i),dfs(x*(n-i)/n,y,n-i)right)mid 0 < i < n right}$$
$$dfs(x,y,n)=minleft{maxleft(dfs(x,y*i/n,i),dfs(x,y*(n-i)/n,n-i)right)mid 0 < i < n right}$$
即横切和竖切。
我们发现，答案与$x,y$具体值无关，而只与它们的比值有关。那么，令$t=frac{x}{y}$，就有
$$dfs(t,n)=minleft{maxleft(dfs(t*i/n,i),dfs(t*(n-i)/{n},n-i)right)mid 0 < i < n right}$$
$$dfs(t,n)=minleft{maxleft(dfs(t/i*n,i),dfs(t/(n-i)*n,n-i)right)mid 0 < i < n right}$$
这时即可记忆化（在bzoj上加了记忆化就从12ms跑到0ms）。
注：由于double自身会有比较误差，便使用了自定义的struct；
而且亲测eps调到0.1在bzoj上也是可以过的（数据好水啊）
附代码：
#include <algorithm>
#include <cstdio>
#include <map>
using std::max;
using std::min;
const double eps = 1e-6;
struct Double{
double x;
Double(double x = .0):x(x) {}
bool operator<(const Double c)const{
return x + eps < c;
}
operator double()const{
return x;
}
};
std::map<Double, double> Map[11];
double dfs(Double t, int n) {
if (n == 1) {
if (t > 1.0) return t;
return 1.0 / t;
}
if (Map[n].count(t)) return Map[n][t];
double &ans = Map[n][t];
ans = 1e15;
for (int i = 1; i <= n / 2; ++i) {
double ans1 = max(dfs(t / n * i, i), dfs(t / n * (n - i), n - i));
double ans2 = max(dfs(t * n / i, i), dfs(t * n / (n - i), n - i));
ans = min(ans, min(ans1, ans2));
}
return ans;
}
int main() {
double x, y;
int n;
scanf("%lf%lf%d", &x, &y, &n);
printf("%.6lfn", dfs(x / y, n));
return 0;
}
- 还没有人评论，欢迎说说您的想法！
客服
