BZOJ1024洛谷P4160 [SCOI2009]生日快乐

news/2024/11/24 6:58:34/

搜索等分点,看在哪部分找就行了

代码

//By AcerMo
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double M=1e9+7;
int n;
double a,b;
double minn(double x,double y)
{if (x<y) return x;else return y;
}
double dfs(double x,double y,int cnt)
{if (x<y) swap(x,y);if (cnt==1) return x/y;double ans=M;for (int i=1;i<=cnt/2;i++){ans=minn(ans,max(dfs(x*i/cnt,y,i),dfs(x*(cnt-i)/cnt,y,cnt-i)));ans=minn(ans,max(dfs(x,y*i/cnt,i),dfs(x,y*(cnt-i)/cnt,cnt-i)));}return ans;
}
signed main()
{cin>>a>>b>>n;double ans=M;if (a<b) swap(a,b);if (n==1) return printf("%.6lf",a/b),0;for (int i=1;i<=n/2;i++){ans=minn(ans,max(dfs(a*i/n,b,i),dfs(a*(n-i)/n,b,n-i)));ans=minn(ans,max(dfs(a,b*i/n,i),dfs(a,b*(n-i)/n,n-i)));}printf("%.6lf",ans);return 0;
}

 


http://www.ppmy.cn/news/325677.html

相关文章

洛谷 P4160 [SCOI2009]生日快乐

PS&#xff1a;如果读过题了可以跳过题目描述直接到题解部分 提交链接&#xff1a;洛谷 P4160 [SCOI2009]生日快乐 题目 题目描述 windy 的生日到了&#xff0c;为了庆祝生日&#xff0c;他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。 现在包括 windy&#xff0c…

BZOJ.4160.[NEERC2009]Exclusive Access 2(状压DP Dilworth定理)

BZOJ DAG中&#xff0c;根据\(Dilworth\)定理&#xff0c;有 \(最长反链最小链覆盖\)&#xff0c;也有 \(最长链最小反链划分数-1\)&#xff08;这个是指最短的最长链&#xff1f;并不是很确定-&#xff09;&#xff0c;即把所有点划分成最少的集合&#xff0c;使得集合内的点两…

luogu P4160 [SCOI2009]生日快乐

传送门 考虑因为每个人的蛋糕体积要相等,如果切了一刀,那么要使得分当前蛋糕的人根据分成的两部分蛋糕的体积分成两部分人,所以假设当前有n人,切的这一刀要是在x或y的\(\frac{k}{n}(k\in N_,k\in [1,n])\)处,然后两边分别有\(k\)和\(n-k\)个人分,所以分治做下去救星了 更多内容…

2023-06-11 LeetCode每日一题(从链表中删去总和值为零的连续节点)

2023-03-29每日一题 一、题目编号 1171. 从链表中删去总和值为零的连续节点二、题目链接 点击跳转到题目位置 三、题目描述 给你一个链表的头节点 head&#xff0c;请你编写代码&#xff0c;反复删去链表中由 总和 值为 0 的连续节点组成的序列&#xff0c;直到不存在这样…

[BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理

Description 给出 N 个点M 条边的无向图&#xff0c;定向得到有向无环图&#xff0c;使得最长路最短。 N ≤ 15, M ≤ 100 Solution 大家都知道Dilworth定理的其中一个内容&#xff1a;最小路径覆盖最长反链。 实际上与之相似的是&#xff1a;最长路最小反链划分数。 这个东…

P4160 [SCOI2009]生日快乐

传送门 一看 $n$ 这么小&#xff0c;搜就完事了... 因为最后每块小蛋糕面积固定&#xff0c;所以每次切完面积都必须是小蛋糕面积的倍数 那么最多只有第一次有 $10$ 个位置&#xff0c;之后越来越少&#xff0c;复杂度很低 然后注意不要乱剪枝...&#xff0c;每次切不一定只切长…

hdu4160 Dolls

http://www.elijahqi.win/2017/12/31/hdu4160-dolls/ ‎ Problem Description Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some…

hdoj 4160 Dolls

http://acm.hdu.edu.cn/showproblem.php?pid4160 转化为二分图的最小路径覆盖问题。 那么答案就是n-最大匹配数 View Code #include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #include<vector> #define maxn 1000…