BZOJ 1024 [SCOI2009]生日快乐

DFS爆搜

首先可以确定每个人分到的面积S，然后DFS枚举怎么切，估计复杂度应当是 O(2n1∗2n2∗2n22∗⋯⋯) ，n很小，所以logn很小，可以随便玩

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; double s, x, y, ans; double dfs(double x, double y, int need) { if(need==1) { return max(x,y)/min(x,y); } double ret = 23333333333.0;; for(int i = 1; i < need; i++) { double ss = s*i, z = ss/x; double p1 = max(dfs(x,z,i), dfs(x,y-z,need-i)); z=ss/y; double p2 = max(dfs(z,y,i), dfs(x-z,y,need-i)); ret=min(ret,min(p1,p2)); } return ret; } int main() { int n; scanf("%lf%lf%d",&x,&y,&n); s = x * y / n; printf("%lf\n",dfs(x,y,n)); return 0; }