题目链接：http://poj.org/problem?id=1190 题目大意：要制作一个体积为Nπ的M层蛋糕，每层都是圆柱体。设从下往上数第i层蛋糕半径为R[i], 高度为H[i]。当i<M时，要求R[i]>R[i+1]且H[i]>H[i+1]。并使得外表面（最下一层的下底面除外）的面积Q最小。令Q = Sπ，答案输出S。N<=10000，M<=20。 题目分析： 1.显然这样的数据范围想到的第一件事儿就是搜索，毕竟M只有20. 2.于是我们就要枚举每一层的R和H了，但显然只这样暴力的枚举肯定是会TLE的，所以我们必须要想办法优化。 3.优化的思路：
首先，R和H的最大值不能超过上一层的R-1和H-1。并且，R和H不能小于层数，因为第1层最小最小R和H都是1和1，到第flo层时R和H自然不能小于层数。对于H还有其他的限制条件，因为V=πR^2*H，所以H<=V(剩余体积)/(R * R)（保留整数）。因为这道题离谱的数据范围，所以在有效范围内从大往小枚举速度更快。如果S(当前侧面积)>ans，返回如果V(当前体积)+V(剩下的所有层的最小体积)>N，返回如果V(当前体积)+V(剩下的所有层的最大体积)<N，返回2∑H[k] * R[k]=2/R[flo] * ∑H[k] * R[k] * R[flo]>=2/R[flo] * ∑H[k] * R[k]^2=2 * (N-V(剩下的体积))/R[flo](这个没有找出来也能过) 正解程序： #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #define inf 0x7ffffff using namespace std; typedef long long ll; ll n,m,ans=inf; ll least[30],ano[30]; inline void dfs(ll flo,ll R,ll H,ll nowv,ll temp) { if(nowv+flo*R*R*H<n) return; if(nowv+least[flo]>n) return; if(temp+ano[flo]>ans || temp+2*(n-nowv)/R>ans) return; if(flo==0) { if(nowv==n) ans=min(temp,ans); return; } double x=sqrt((double(n-nowv))); ll c1=x; for(ll i=min(c1,R-1);i>=flo;i--) { ll c2=(n-nowv)/(i*i); for(ll j=min(c2,H-1);j>=flo;j--) { if(flo==m) dfs(flo-1,i,j,nowv+i*i*j,temp+2*i*j+i*i); else dfs(flo-1,i,j,nowv+i*i*j,temp+2*i*j); } } } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=m;i++) least[i]=least[i-1]+i*i*i; for(ll i=1;i<=m;i++) ano[i]=ano[i-1]+2*i*i; dfs(m,n+1,n+1,0,0); if(ans==inf) printf("0"); else printf("%lld",ans); return 0; }