首页 > 代码库 > bzoj 1024 SCOI2009 生日快乐

bzoj 1024 SCOI2009 生日快乐

     一上来没思路……

    但是由于每块蛋糕面积相等,又因为每次切必须切成两半,所以每半的面积都是每块蛋糕面积的倍数。

    枚举切下来的蛋糕应该还被分为多少块蛋糕,计算切割的地方,分X 和 Y, 递归搜索。

    上代码:

#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define inf 0x7f7f7f7fusing namespace std;int num;double X, Y;double dfs(int n, double x, double y){    if (n == 1) return max(x, y) / min(x, y);    double d = (double)n;    double ans = inf;    for (int i = 1; i < n; ++i)    {        ans = min(ans, max(dfs(i, x/d*i, y), dfs(n-i, x/d*(n-i), y)));        ans = min(ans, max(dfs(i, x, y/d*i), dfs(n-i, x, y/d*(n-i))));    }    return ans;}int main(){    scanf("%lf%lf%d", &X, &Y, &num);    printf("%lf\n", dfs(num, X, Y));    return 0;}

 

bzoj 1024 SCOI2009 生日快乐