G - 生日蛋糕 - 秒客网

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。

令Q = Sπ

请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。

（除Q外，以上所有数据皆为正整数）

Input

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

Output

仅一行，是一个正整数S（若无解则S = 0）。

Sample Input

100

2

Sample Output

Hint

圆柱公式

体积V = πR 2H

侧面积A' = 2πRH

底面积A = πR 2

靠深搜，一开始想从上往下搜，记录之类的比较方便，但是那样要搜太多情况了，10000的时候就会t，所以只能从下往下搜，还有，蛋糕是上面的连着下面的，所以上面的蛋糕只要计算侧面积

还有剪枝，除去那些不可以的条件，1，当剩下的半径和高即使去最大也不能满足剩下体积的时候，2，当剩下即使取最大半径使高最小，面积也大于之前所取的面积时。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include <iomanip>

#include<cmath>

#include<float.h>

#include<string.h>

#include<algorithm>

#define sf scanf

#define pf printf

#define pb push_back

#define mm(x,b) memset((x),(b),sizeof(x))

#include<vector>

#include<map>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

typedef long long ll;

typedef long double ld;

typedef double db;

const ll mod=1e9+100;

const db e=exp(1);

using namespace std;

const double pi=acos(-1.0);

int V,S=0,m;

bool check1(int deep,int s,int lv,int r,int h)//太大了

{

	if(lv<r*r*h)

	return false;

	if(S&&(s+2*lv/r)>S)

	return false;

	return true;

}

void dfs(int deep,int lv,int s,int r,int h)

{

	if(deep==0&&lv==0)

	{

		if(S==0)

		S=s;

		else

		S=min(S,s);

		return ;

	}

	if(deep*(r-1)*(r-1)*(h-1)<lv&&deep!=m)//接下来就算取最大高和半径都弥补不上剩下体积

	 return ;

	if(deep<=0||lv<0||(s>=S&&S))//不可以出现的情况

        return ;

		per(i,r-1,deep)

		{

			per(j,h-1,deep)

			{

				//cout<<"1";

				if(!check1(deep,s,lv,i,j))

				continue;

				if(deep==m)

				dfs(deep-1,lv-i*i*j,s+i*2*j+i*i,i,j);

				else

				dfs(deep-1,lv-i*i*j,s+i*2*j,i,j);

			}

		}

}

int main()

{

	cin>>V>>m;

	int k=(int)sqrt(V);

	dfs(m,V,0,k+1,10000);//一开始取10000是取n，但是超过这个数字，差不多都会超时，也不可能出现取非常高的表面积还小，所以取这么大就够了

	cout<<S;

	return 0;

}

G - 生日蛋糕