洛谷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==0)//如果到顶层 { if(v1==n&&s1<ans)//且体积满足题目要求 并且表面积小于原来的最优 ans=s1; return; } if(s1+s[now]>ans) return;//当前表面积+下一层表面积如果超过最优值就退出 if(v1+v[now]>n) return;//当前体积+下一层体积如果超过总体积就退出 if(s1+2*(n-v1)/r>ans) return;//假设剩余所有的体积都用来做下一层那么此时下一层的体积是最大 //而半径会最大，从而表面积最小 for(int i=r-1;i>=now;i--)//从下一层最小半径开始枚举寻找合适的半径 { if(now==m) s1=i*i;//如果是底层 表面积为“顶面 ” int h1=min(h-1,(n-v1-v[now-1])/(i*i));//总体积-已用体积-下一层体积除底面积为高与下一层最大高度比较 for(int j=h1;j>=now;j--) { dfs(now-1,s1+2*i*j,v1+i*i*j,i,j); } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { v[i]=v[i-1]+i*i*i;//前i层+自身的最大体积 s[i]=s[i-1]+2*i*i;//i层+自身的最大表面积 } dfs(m,0,0,sqrt(n),n); if(ans==inf) cout<<0; else cout<<ans; }