P4160 [SCOI2009]生日快乐

传送门

一看 $n$ 这么小，搜就完事了...

因为最后每块小蛋糕面积固定，所以每次切完面积都必须是小蛋糕面积的倍数

那么最多只有第一次有 $10$ 个位置，之后越来越少，复杂度很低

然后注意不要乱剪枝...，每次切不一定只切长的边，枚举位置时因为左右两边是对称的所以只要枚举一半

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
typedef double db;
inline int read()
{int 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<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f;
}
const db eps=1e-8,INF=1e9;
db X,Y,n,ans;
db dfs(db x,db y)
{if(fabs(x*y-X*Y/n)<eps) return max(x/y,y/x);int m=x*y/(X*Y/n)+eps; db res=INF;for(int i=1;i<=m/2;i++){db t1=max(dfs(x/m*i,y),dfs(x/m*(m-i),y));db t2=max(dfs(x,y/m*i),dfs(x,y/m*(m-i)));res=min(res,min(t1,t2));}return res;
}
int main()
{scanf("%lf%lf%lf",&X,&Y,&n);printf("%.6f\n",min(dfs(X,Y),dfs(Y,X)));return 0;
}