题解 | #[SCOI2009]生日快乐#

dfs(x,y,n)表示当前切的矩形长x宽y，需要切成n块;

每次切的时候，我们可以选择在x/ni处竖切，也可以在y/ni处横切(i=1，2...n/2);

每次切后会产生两块矩形，我们可以通过这两块矩形的面积来确定接下来要将其分成多少块矩形(即新的n);

#include<iostream>
using namespace std;
double x,y;
int n;

double dfs(double x,double y,int n)
{
    if(n<=1) 
    {
        return max(x/y,y/x);
    }
    double res=1e5;
    for(int i=1;i<=n/2;i++)
    {
        res=min(res,max(dfs(x,y/n*i,i),dfs(x,y/n*(n-i),n-i)));
        res=min(res,max(dfs(x/n*i,y,i),dfs(x/n*(n-i),y,n-i)));
    }
    return res;
}    
int main()
{
    scanf("%lf%lf%d",&x,&y,&n);
    printf("%.6lf",dfs(x,y,n));
}