【每日一题】 [SCOI2009]生日快乐

递归

数据范围较小，直接递归解决。
考虑将当前蛋糕分成left块：
当left==1时，返回长与宽的比值；
当left>1时，若沿着当前蛋糕的某一条边切割总共有n/2种切割方法（考虑对称性），沿着长和宽总共有(n/2)*2种切割方法；对于当前蛋糕的每一种切割方法，递归考虑其切割后的两个蛋糕，得到二者切割后能够生成的小蛋糕中长宽比值最大者（从一种切割方法生成的n块蛋糕中找到长宽比值最大的一块）；对于当前蛋糕的所有切割方法，从中选出每种比值最大的小蛋糕的最小比值，返回该比值。

值得注意的是，对于递归中生成的所有最小蛋糕，不能一味取其最大比值或最小比值；要分清楚递归过程中，哪些步骤是在选择切分方法（取最小），哪些步骤是在切分（取最大）。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=11e9+7;
const int maxn=1e5+9;
const ll maxx=1e12+9;

int x,y,n;
double arc;

double dfs(int left,double a,double b)
{
    if(a>b) swap(a,b);
    if(left==1) return b/a;
    double tmp=inf1;
    double la=arc/a,lb=arc/b;
    for(int i=1;i<=left/2;i++)
        tmp=min(tmp,max(dfs(i,la*i,a),dfs(left-i,b-la*i,a)));
    for(int i=1;i<=left/2;i++)
        tmp=min(tmp,max(dfs(i,lb*i,b),dfs(left-i,a-lb*i,b)));
    return tmp;
}
int main()
{
    scanf("%d%d%d",&x,&y,&n);
    arc=x*y*1.0/n;
    printf("%.6lf\n",dfs(n,x,y));
}