NC20272 简单dfs

给一块矩形蛋糕，要求切成等面积的n个矩形，且长宽比的最大值最小。
首先题目中的切n-1刀是很自然的，不需要去管，因为每一刀只能把一块切成两块，所以任何分割情况都是合法的。接下来看到n最大是10，那就很可能是指数级或阶乘级的算法，自然想到dfs。怎么搜呢？我们枚举每一刀的位置即可，对于当前矩形假如要把它切成k块，下一刀的取法只有2*(k-1)种方案，取最小的一种即可

#include<bits/stdc++.h>
using namespace std;

double dfs(double x,double y,double k){
    if(k==1){
        return max(x,y)/min(x,y);
    }
    double res=10000;
    for(int i=1;i<k;i++){
        res=min(res,max(dfs(x/k*i,y,i),dfs(x/k*(k-i),y,k-i)));
        res=min(res,max(dfs(x,y/k*i,i),dfs(x,y/k*(k-i),k-i)));
    }
    return res;
}

int main(){
    int n;
    double x,y;
    cin>>x>>y>>n;
    cout<<fixed<<setprecision(6)<<dfs(x,y,n)<<endl;
}