每日一题 8月17日 [SCOI2009]生日蛋糕 dfs

题目描述：
有个X*Y的蛋糕，现在要均分成N块。每次切一刀都会把一个蛋糕分成2块，问这样切N-1次，得到的蛋糕中长宽比的最大值的最小值是多少。

思路：
N<=10
数据很小。考虑dfs。
由于每个人分到蛋糕面积需要相同，显然我们不能随便切。
假设当前蛋糕为X * Y，需要分N块。那么如果我们如果竖着切（分成左右两块），我们只能选择X/N * i的位置切。横着切（分成上下两块）同理，只能选择Y/N * i的位置切。这里i是整数。
假设我们竖着切在X/N * i的位置上，我们会分成左右两块，而且我们可以分别确定左右两块要切多少刀。左边需要i-1刀分成i块，右边需要N-i-1刀分成N-i块。
那么我们可以令dfs(x,y,k)表示x*y的蛋糕需要分成k块。那么我们考虑当前一刀横着或者竖着切，分成左右（上下）两块后继续dfs。当蛋糕只剩1块时就说明搜到底了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
double X,Y;
double S,bizhi,ans=100000;
double dfs(double x,double y,int k){
    double ans=100000;
    if(k==1){
      //  cout<<x<<' '<<y<<endl;
        return max(x,y)/min(x,y);
    }
    for(int i=1;i<k;i++){
        double cut=i*x/k;
        //if(cut>=x)break;
        ans=min(ans,max(dfs(cut,y,i),dfs(x-cut,y,k-i)));
    }
    for(int i=1;i<k;i++){
        double cut=i*y/k;
      //  if(cut>=y)break;
        ans=min(ans,max(dfs(x,cut,i),dfs(x,y-cut,k-i)));
    }
    return ans;
}
int main()
{
    cin>>X>>Y>>n;
    S=X*Y;
    S/=n;
    k=1;

    printf("%.6f\n",dfs(X,Y,n));
    return 0;
}