洛谷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;
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9715857.html
相关资源：JAVA上百实例源码以及开源项目
