洛谷P1731：https://www.luogu.org/problemnew/show/P1731
思路
三重剪枝
- 当前表面积+下一层表面积如果超过最优值就退出
- 当前体积+下一层体积如果超过总体积就退出
- 假设剩余所有的体积都用来做下一层那么此时下一层的体积是最大 而半径会最大 从而表面积最小（定理：当体积一定时 半径越大 表面积越小）
每次枚举半径和高时 是从下一层的半径和高到还剩下的层数 因为每层都要比下面大1
代码
#include<iostream>
#include<cmath>
using namespace std;
#define maxn 30
#define inf 2147483647
int n,m,ans=inf;
int v[maxn],s[maxn];
void dfs(int now,int s1,int v1,int r,int h)//now为当前层数 s1为已经有的表面积 v1为已经有的体积
//r为当前半径 h为当前高度
{
if(now==)//如果到顶层
{
if(v1==n&&s1<ans)//且体积满足题目要求 并且表面积小于原来的最优
ans=s1;
return;
}
if(s1+s[now]>ans) return;//当前表面积+下一层表面积如果超过最优值就退出
if(v1+v[now]>n) return;//当前体积+下一层体积如果超过总体积就退出
if(s1+*(n-v1)/r>ans) return;//假设剩余所有的体积都用来做下一层那么此时下一层的体积是最大
//而半径会最大，从而表面积最小
for(int i=r-;i>=now;i--)//从下一层最小半径开始枚举寻找合适的半径
{
if(now==m) s1=i*i;//如果是底层 表面积为“顶面 ”
int h1=min(h-,(n-v1-v[now-])/(i*i));//总体积-已用体积-下一层体积除底面积为高与下一层最大高度比较
for(int j=h1;j>=now;j--)
{
dfs(now-,s1+*i*j,v1+i*i*j,i,j);
} }
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
v[i]=v[i-]+i*i*i;//前i层+自身的最大体积
s[i]=s[i-]+*i*i;//i层+自身的最大表面积
}
dfs(m,,,sqrt(n),n);
if(ans==inf)
cout<<;
else
cout<<ans;
}