Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题暴搜会超时,剪枝还得减细致一点

Posted by 3208189329 at 2023-04-03 22:02:25 on Problem 1190
In Reply To:这题暴搜会超时,剪枝还得减细致一点 Posted by:110120_119 at 2019-03-27 17:29:24
> /*
> 
> 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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator