【BZOJ1024】【SCOI2009】生日快乐
N=10感觉暴力都能过的样子...
枚举每次切的位置即可。由于N=10，切出来的两块的大小也一定是每人分得大小的整数倍，所以将x*=10!，y*=10!以后就可以直接用整数来做了。还可以开map记忆化。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> Node;
const LL n10=3628800,maxn=10001;
const double eps=1e-5;
map<Node,double> M;
double f(LL x,LL y,int n)
{
if (n==1) return max((double)x/y,(double)y/x);
if (n==2) return min(max((double)x/(y*2),(double)(y*2)/x),max((double)y/(x*2),(double)(x*2)/y));
if (x>y) swap(x,y);
Node v;
v.first=x;v.second=y;
if (M[v]) return M[v];
double res=1e10;
for (int k=1;k<=(n>>1);k++)
{
res=min(res,max(f(x,y*k/n,k),f(x,y-y*k/n,n-k)));
res=min(res,max(f(x*k/n,y,k),f(x-x*k/n,y,n-k)));
}
M[v]=res;
return res;
}
int main()
{
int n;
LL x,y;
scanf("%lld%lld%d",&x,&y,&n);
x*=n10;y*=n10;
printf("%.6f\n",f(x,y,n));
}
评论 (0)
