牛客—— [SCOI2009]生日快乐 （dfs）

牛客—— [SCOI2009]生日快乐 （dfs）
原题链接：https://ac.nowcoder.com/acm/problem/20272
题意：

给定一个矩形蛋糕，只能平行x轴或y轴切n-1刀得到面积相等的n块蛋糕，求n块蛋糕的长边与短边比值的最大值最小的值。

思路：

被题意迷惑以为是二分。

因为数据范围很小，考虑状压dp或dfs。

我用的是dfs，因为感觉double类型的dp并不好转移。
考虑切每一刀的时候是平行x轴切还是平行y轴切，然后再枚举一下切的位置，当只剩一块的时候返回答案。

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
#define I_int ll
#define modl 19260817*19890604-19491001
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}

int x,y,n;
//长 宽 剩余切的次数
double dfs(double x,double y,int n){
    if(n==1) return max(x,y)/min(x,y);///返回答案
    double res=1e18;
    for(int i=1;i<n;i++){//枚举切的位置
        double tmp1=max(dfs(x/n*i,y,i),dfs(x/n*(n-i),y,n-i));//把长切开，平行于宽切
        double tmp2=max(dfs(x,y/n*i,i),dfs(x,y/n*(n-i),n-i));//把宽切开，平行于长切
        res=min(res,max(tmp1,tmp2));//题意
    }

    return res;
}

int main(){
    x=read(),y=read(),n=read();
    double res=dfs(x,y,n);
    printf("%.6f\n",res);
    return 0;
}