牛客每日一题 7月15日-生日快乐(DFS)
程序员文章站
2024-02-21 18:59:04
...
生日快乐
题目
题解
大概意思给你一个nm的矩形,切成n等分,并且长宽比的最大值最小。
dfs的方向就是我们枚举每一刀的位置即可,对于当前矩形假如要把它切成k块,下一刀的取法只有2(k-1)种方案,取最小的一种即可。
代码
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
double dfs(double x, double y, int n) {
if(n == 1)
return max(x,y)/min(x,y);
double ans = 0x7f7f7f;
for(int i = 1; i < n; i++) {
ans = min(ans, max(dfs(x/n*i, y, i), dfs(x/n*(n-i), y, n-i))); //切左边的
ans = min(ans, max(dfs(x, y/n*i, i), dfs(x, y/n*(n-i), n-i))); //切右边的
}
return ans;
}
int main() {
double x, y;
int n;
scanf("%lf%lf%d", &x, &y, &n);
double num = dfs(x,y,n);
printf("%.6lf\n", num);
return 0;
}
上一篇: centos7关闭防火墙
下一篇: 忘记MySQL的root密码该怎么办