欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客每日一题 7月15日-生日快乐(DFS)

程序员文章站 2024-02-21 18:59:04
...

生日快乐

题目

生日快乐

牛客每日一题 7月15日-生日快乐(DFS)

题解

大概意思给你一个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;
}