题解 P4160 【[SCOI2009]生日快乐】
浅色调
·
·
题解
Solution：
本题不需要多想直接dfs。
首先我们假设当前的矩形长为x，宽为y，要分出k块，那么不难想到分出的一块的长mx最短为x/k，宽my最短为y/k，而且每次切的长度一定是mx的倍数或my的倍数（很好理解，不是倍数就无法保证之后切出至少长mx的矩形或宽my的矩形，可以自行画图）。
于是我们递归搜索，每次切长或者宽，在分出的两块中取比值的最大值，更新最大值的最小值，返回就OK了。
### 代码：
```cpp
#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(double (i)=(a);(i)<=(b);(i)++)
using namespace std;
int n,x,y;
il double dfs(double x,double y,int k){
if(k==1){return max(x,y)*1.0/min(x,y);}
double ans=233333333,mx=x*1.0/k,my=y*1.0/k,t1,t2;
For(i,1,k/2){
t1=max(dfs(mx*i,y,i),dfs(x-mx*i,y,k-i));
t2=max(dfs(x,my*i,i),dfs(x,y-my*i,k-i));
ans=min(ans,min(t1,t2));
}
return ans;
}
int main(){
cin>>x>>y>>n;
printf("%.6lf",dfs(x,y,n));
return 0;
}
```