/*

104K 63MS
*/
#include<cstdio>
#include<cmath>
#pragma warning (disable:4996)
using namespace std;

int N, M;					// N表示体积，M表示层数
int minV[25], minA[25];		// minV[i]表示从最上面一层到第i层最小的体积，minA[i]表示从最上面一层到第i层最小的侧面积
int area;					// 搭建蛋糕过程中，当前的总面积
int minArea;				// 最小的表面积

int maxVFOR_RH(int m,int r, int h )		//第m层时，最大半径r，最大高度h
{
	int maxv=0;
	for (int i = 0; i < m; i++)		//从该层往上，每一层都按照最大的半径和高度计算，求出在第m层时，上面最大体积
	{
		maxv += (r - i)*(r - i)*(h - i);
	}
	return maxv;
}

void dfs(int _V, int _M, int maxR, int maxH)
{
	if (_M == 0)		// 若刚好搭建好，即剩余层数为0
	{
		if (_V == 0)	// 体积刚好满足
		{
			minArea = area > minArea ? minArea : area;	// 更新最小表面积
		}
		return;
	}

	if (maxVFOR_RH(_M, maxR, maxH) < _V)	//剪枝，若从该层开始往上，所构建的最大蛋糕体积 小于 剩余蛋糕体积，则无法构建
		return;

	// 剪枝，若剩余体积小于0或者小于剩下构建所需的最小体积，或者最大半径、高度小于当前层数，则都不需要继续构建了
	if (_V < 0 || _V < minV[_M] || maxR < _M || maxH < _M)
		return;

	if (area + minA[_M] >= minArea)			// 剪枝，若当前面积加上剩下蛋糕最小侧面积 大于 最小的表面积，这个方案不是最优
		return;

	for (int rr = maxR; rr >= _M; rr--)		// 半径从最大的尝试，最小为当前层数
	{
		if (_M == M)						// 若当前构建的层数是最底层(即第一次构建)，则初始化area，使其等于底层的上表面积
			area = rr * rr;
		for (int hh = maxH; hh >= _M; hh--)	// 双重循环，遍历每一层中每一个半径与高度的所有情况
		{
			area += 2 * rr * hh;			// 当前面积需要加上侧面积

			//printf("_M = %d  rr=%d  hh=%d  area=%d\n", _M, rr, hh,area);

			dfs(_V - rr * rr * hh, _M - 1, rr - 1, hh - 1);	

			area -= 2 * rr * hh;			//复原当前状态
		}
	}

}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	while (scanf("%d %d", &N, &M) != EOF)
	{
		//蛋糕是从下往上构建的
		minArea = 1 << 30;		//最小表面积初始化成很大的值
		minV[0] = 0, minA[0] = 0;

		for (int i = 1; i <= M; i++)				//从顶往下，记录到达每一层时，最小的体积以及最小的侧面积
		{
			minV[i] = minV[i - 1] + i * i * i;		//当层体积为  R*R*R == i*i*i
			minA[i] = minA[i - 1] + 2 * i * i;		//侧面积等于  2*R*H == 2*i*i
		}

		if (minV[M] > N)			//如果从顶到第M层所需的最小体积小于给的N,则不可能构成蛋糕
		{
			printf("0\n");	
		}
		else
		{
			int maxR, maxH;								//求出最底层的最大半径和最大高度
			maxH = (N - minV[M - 1]) / (M * M) + 1;		//底层最大高度=（所有体积-上面最小体积）/（底面积） + 1；
			maxR = sqrt(((N - minV[M - 1])) * 1.0 / M) + 1;

			//printf("maxH=%d maxR=%d\n", maxH, maxR);

			area = 0;					//当前总面积为0
			dfs(N, M, maxR, maxH);		//剩余体积N   剩余层数M  当前最底层的最大半径和高度
			
			if (minArea == 1 << 30)
				printf("0\n");
			else
				printf("%d\n", minArea);
		}

	}

	return 0;
}

• Re:这题暴搜会超时，剪枝还得减细致一点 (4) retown 2019-07-02 21:12:57
• Re:这题暴搜会超时，剪枝还得减细致一点 (2616) 3208189329 2023-04-03 22:02:25