洛谷P4160 [SCOI2009]生日快乐

· · 题解

这题看过去，一时间还真没有什么头绪……

但是，经过洛谷题解和CSDN的各位巨佬的讲解之后，我也初步明白了怎么做。

这题，其实是一个DFS（或是递归）标准题。其实，我们只需要设置状态DFS(x,y,n)表示将长为x,宽为y的长方形蛋糕，切成n块的最小比值。

由于每一块蛋糕的面积必须是相等的，所以当我们要切成n块时，长最小是x/n，宽最小是y/n。所以，我们只要枚举把蛋糕按长和宽切成两块的最大值，取其中的最小值即可。边界条件：n==1时，返回x/y。

AC代码如下：

#include <bits/stdc++.h>
using namespace std;
double decom(double x,double y,int n)
{
    if(n==1) return max(x,y)/min(x,y);
    double dx=x/n,dy=y/n;
    double ans=233333333.00000;
    for(double i=1.0;i<=(n/2.0);i+=1.0)
    {
        double t=max(decom(dx*i,y,i),decom(x-dx*i,y,n-i));
        double p=max(decom(x,dy*i,i),decom(x,y-dy*i,n-i));
        ans=min(ans,min(t,p));
    }
    return ans;
}
int main()
{
    double x,y;
    int n;
    cin>>x>>y>>n;
    printf("%.6lf",decom(x,y,n));
}