首页 > 代码库 > BZOJ 1024: [SCOI2009]生日快乐

BZOJ 1024: [SCOI2009]生日快乐

Description

将一个 \(x\times y\) 的矩形分成 \(n\) 块,让最长边:最短边 最小.

Sol

搜索.

\(n\) 只有 \(10\) 写一个类似于记搜的东西就好了.

Code

/**************************************************************    Problem: 1024    User: BeiYu    Language: C++    Result: Accepted    Time:220 ms    Memory:1288 kb****************************************************************/ #include<cstdio>#include<iostream>using namespace std; int x,y,n; double DFS(double x,double y,int d){    if(d == 1) return max(x,y)/min(x,y);    double res=23333333.33;    for(int i=1;i<d;i++) res=min(res,max(DFS(x,y*i/d,i),DFS(x,y*(d-i)/d,d-i)));    for(int i=1;i<d;i++) res=min(res,max(DFS(x*i/d,y,i),DFS(x*(d-i)/d,y,d-i)));    return res;}int main(){    cin>>x>>y>>n;    printf("%.6lf\n",DFS(x,y,n));    return 0;}

  

BZOJ 1024: [SCOI2009]生日快乐