BZOJ 1024 SCOI 2009 生日快乐 深搜

BZOJ 1024 SCOI 2009 生日快乐 深搜

大家好,又见面了,我是全栈君。

题目大意:有一块蛋糕,长为X,宽为Y。如今有n个人来分这块蛋糕,还要保证每一个人分的蛋糕的面积相等。求一种分法,使得全部的蛋糕的长边与短边的比值的最大值最小。

思路:刚拿到这个题并没有什么思路。可是定睛一看。(n <= 10),额。。能够乱搞了。。。

直接爆搜就能够水过。传三个參数,代表当前的长和宽,还有当前块须要被分成几块,然后随便乱搞就能够水过了。。

CODE:

#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

int X,Y,cnt;

double DFS(double x,double y,int step);

int main()
{
	cin >> X >> Y >> cnt;
	cout << fixed << setprecision(6) << DFS(X,Y,cnt) << endl;
	return 0;
}

double DFS(double x,double y,int step)
{
	if(step == 1) {
		if(x < y)	swap(x,y);
		return x / y;
	}
	double _x = x / step,re = 10000.0;
	for(int i = 1;i < step; ++i) {
		double temp = DFS(_x * i,y,i);
		temp = max(temp,DFS(x - _x * i,y,step - i));
		re = min(re,temp);
	}
	double _y = y / step;
	for(int i = 1;i < step; ++i) {
		double temp = DFS(x,_y * i,i);
		temp = max(temp,DFS(x,y - _y * i,step - i));
		re = min(re,temp);
	}
	return re;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115892.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号