bzoj 1024 [ SCOI 2009 ] 生日快乐 —— 递归
2024-08-23 08:50:36
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1024
因为每次把一块切成两块,所以可以枚举从哪里切开,然后递归求解;
一开始用了不太对的贪心思路,想着一定去切较长边,但看来不一定。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int inf=1e9;
int a,b,n;
double ans=inf,s;
double dfs(double x,double y,int cnt)
{
// printf("x=%.2lf y=%.2lf cnt=%d\n",x,y,cnt);
if(x<y)swap(x,y);
double ret=inf;
if(cnt==)return x/y;
for(int i=;i<cnt;i++)
{
// double k=(x*y-i*s)/y;
double k=x*i/cnt;
ret=min(ret,max(dfs(k,y,i),dfs(x-k,y,cnt-i)));
// k=(x*y-i*s)/x;
k=y*i/cnt;
ret=min(ret,max(dfs(x,k,i),dfs(x,y-k,cnt-i)));
}
return ret;
}
int main()
{
scanf("%d%d%d",&a,&b,&n);
s=1.0*a*b/n;
if(a<b)swap(a,b);
// for(int i=1;i<n;i++)
// {
// double k=(1.0*a*b-i*s)/b;
// ans=min(ans,max(dfs(k,b,n-i),dfs(a-k,b,i)));
// }
printf("%.6lf",dfs(a,b,n));
return ;
}
最新文章
- 【转】iframe和父页,window.open打开页面之间的引用
- JavaScript的9个陷阱及评点
- hadoop生态系统的详细介绍
- C语言之指针与数组总结
- BZOJ_1606_ [Usaco2008_Dec]_Hay_For_Sale _购买干草_(背包)
- Android开发艺术探索(三)——View的事件体系
- poj1837挂砝码
- ★★★★[转载]Python学习笔记一:数据类型转换★★★★
- 前端开发必备之Chrome开发者工具(一)
- 洛谷 P1226 【模板】快速幂||取余运算
- javascript的介绍、javascirpt的存在形式、javascript注释
- js——正则表达式
- 生成树的计数 Matrix-Tree(矩阵树)定理
- 记录Ok6410 sd 启动uboot
- JavaScript中 this 的指向
- flex bison
- 通过Viewpager 来实现微信界面左右滑动。
- Hadoop基础总结
- c++11 继承构造
- mysql 查询所有父级名称