生日蛋糕

https://www.luogu.com.cn/problem/P1731
题目描述

已知蛋糕体积和层数，求表面积的最小值。

输入

第一行为一个整数N(N≤2×10^4)，表示待制作的蛋糕的体积为 Nπ。

第二行为M（M≤15)，表示蛋糕的层数为M。

输出格式

输出一个整数 S为蛋糕的表面积（除下底面外），若无解，输出 0。

注：所有数据均为整数

分析

表面积=最下面一层的底面积加每一层的侧面积=r_1^2+2r_1h_1+2r_2h_2+……+2r_mh_m
体积=r_1^2*h_1+r_22h_2+……+r_m^2h_m

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e9;
void dfs(int x,int s,int v,int r,int h)//x当前层数，s表面积，v剩余体积，r上一层的半径，h上一层的高度
{ 
	if(s>=ans) return;//优化一，当前表面积大于已知最小值
	if(r<m-x+2||h<m-x+2) return;//优化二，因为r、h递减且为整数，保证每一层减一的情况下之后的r和h均大于零，，，有奇效
	if(v/r*2+s>ans) return;//用剩余体积推算之后的最小面积，与已知最小值比较
	if(v==0&&x==m+1)
	{
		ans=min(ans,s);
		return;
	}
	for(int i=r-1;i>0;i--)
		for(int j=h-1;j>0;j--)
		{
			if(v-i*i*j>=0&&x<=m)
			{
				dfs(x+1,s+2*i*j,v-i*i*j,i,j);
			}
		}
}
int main()
{
	
	cin>>n>>m;
	for(int i=sqrt(n);i>0;i--)
	for(int j=n/i/i;j>0;j--)
	{
		dfs(2,i*i+2*i*j,n-i*i*j,i,j);
	}
	cout<<ans;
	return 0;
}