【BZOJ1070】【SCOI2007】修车
【BZOJ2301】【HAOI2011】Problem b

【BZOJ1024】【SCOI2009】生日快乐

Zarxdy34 posted @ 2015年12月20日 14:30 in BZOJ with tags DFS , 275 阅读
    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));
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top