首页 > 代码库 > BZOJ1024 SCOI2009 生日快乐 DFS
BZOJ1024 SCOI2009 生日快乐 DFS
题意：给定一个X*Y的长方形，每次可以平行长或宽切一刀，求切N-1次能得到的最小的N个子长方形中长宽比最大的值。
题解：因为N<=10，DFS乱搞就好
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define INF 66666.0int N;double X,Y;double DFS(double x,double y,int c){ if(c==1){ if(x<y) swap(x,y); return x/y; } double t=x/c,Ans=INF; for(int i=1;i<c;i++){ double r=max(DFS(t*i,y,i),DFS(x-t*i,y,c-i)); Ans=min(Ans,r); } t=y/c; for(int i=1;i<c;i++){ double r=max(DFS(x,t*i,i),DFS(x,y-t*i,c-i)); Ans=min(Ans,r); } return Ans;}int main(){ scanf("%lf %lf %d",&X,&Y,&N); printf("%.6lf\n",DFS(X,Y,N)); return 0;}
BZOJ1024 SCOI2009 生日快乐 DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。