SCOI2009 生日快乐

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2009 生日快乐

Date: Thu Aug 02 09:25:39 CST 2018

In Category: NoCategory

Description：

将一个 $x\times y$ 的矩形切成大小相等的 $n$ 块，使长和宽最大的比值最小。

$1\le x,y\le 10^4$ $1\le n \le 10$

Solution：

先计算出每块蛋糕的面积，然后枚举这一刀两边各几块，再分别计算出沿着长切和沿着宽切这条边的长度然后递归去求，最后两边取个 $max$ ，再和 $ans$ 取 $min$ 即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

double siz;

double dfs(double x,double y,int n)

{

	if(n == 1)return max(x / y,y / x);

	double ans = 100000000000;

	for(int i = 1;i < n;++i)

	{

		ans = min(ans,max(dfs(x,(double)i * siz / x,i),dfs(x,y - (double)i * siz / x,n - i)));

		ans = min(ans,max(dfs((double)i * siz / y,y,i),dfs(x - (double)i * siz / y,y,n - i)));

	}

	return ans;

}

int main()

{

	int x,y,n;

	scanf("%d%d%d",&x,&y,&n);

	siz = (double)x * (double)y / (double)n;

	printf("%.6lf\n",dfs((double)x,(double)y,n));

	return 0;

}

In tag: 算法-搜索

wjh15101051