题解 P4160 【[SCOI2009]生日快乐】
小黑AWM
2019-01-27 19:09:25
屑题，不过窃以为题面具有较强的误导性，容易让人想偏，第一眼二分答案，后来发现不是很具有单调性，然后又因为读错题面写了个二进制枚举（以为只能一块一块切过去切的每块都是$1/n$
读懂之后并不是很难。看到数据范围，考虑搜索。
考虑*只有两种切法*：
### 即沿着x切或沿着y切
并且对于没一刀切下去，必然把这块蛋糕切成两块，又由于最后切完之后的每块蛋糕都是$1/n$的面积。
易知切出来的两块蛋糕必定是$k/n + (n-k)/n , k \in N$
所以我们便可以枚举$k$进行多情况拓展。
可以顺手加个简单的记忆化优化，虽然并不是很有必要。
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<double,pair<double ,int> > pddi;
double x, y;
int n;
map<pair<double,pair<double ,int> >, double> memory;
double dfs(double x, double y, int num){
pddi temp = make_pair(x,make_pair(y, num));
if(memory.count(temp))
return memory[temp];
double ans = 1000000.0;
if(num == 1)
return max(x, y)/min(x, y);
for(int i = 1; i <= num-1; i++)
ans = min(ans, max(dfs(x, y*i/num, i), dfs(x, y*(num-i)/num, num-i)));//切y有两种状态，切两分
for(int i = 1; i <= num-1; i++)
ans = min(ans, max(dfs(x*i/num, y, i), dfs(x*(num-i)/num, y, num-i)));
memory[temp] = ans;
return ans;
}
int main(){
scanf("%lf%lf%d", &x, &y, &n);
printf("%.6lf", dfs(x, y, n));
return 0;
}
```