写了注释,求条
CODE:
//---------------juruo_xyu---------------------
#include<bits/stdc++.h>
using namespace std;
int mis[21],miv[21];//每一层的最小表面积与体积
int h[21],r[21];
int n,m;
int sum=INT_MAX;//要求出来的 最小 表面积和
void dfs(int s/*已经搜出来的表面积*/,int v/*已经搜出来的体积*/,int k/*第k层*/){
if(v+miv[k]>n)return ;
//合理化剪枝①:如果当前搜出来的体积加上剩下的最小体积
//(从下往上搜)还要大于n就直接结束这一个分支
if(s+mis[k]>=sum)return ;
//合理化剪枝②:如果此时搜出来的表面积加上剩下的最小表
// 面积还要大于等于目前的最小表面积和
//就可以说再继续搜索是无意义的,直接结束该分支
//这里需要一个数学推导过程,合理化剪枝 ③
//利用h与r的数组,1^^dep-1层的体积可以表示为n-v = h[k]*r[k]*r[k] k(1---dep-1)
//表面积为 2*h[k]*r[k] k(1---dep-1)
//2*h[k]*r[k]=2*h[k]*r[k]*r[dep]/r[dep] >= 2*h[k]*r[k]*r[k]/r[dep] >=2*(n-v)/r[dep]
//2*(n-v)/r[dep]+s>=sum
if(s+2*(n-v)/r[k+1]>=sum){//如果当前的s加上 2*剩下的体积除以上一层的r
return;//直接返回
}
if(k==0){//如果搜完了这一次
if(v==n){//如果体积符合要求
sum=s; //最小表面积和更新
}
return ;//达到目标
}
//开始搜索
for(int i=min((int)(sqrt(n-v)),r[k+1]-1);i>=k;i--){
//上下界剪枝:
//上界:sqrt((需要的体积-目前的体积)/h的最小值)和
//上一层的半径减去最小的正整数1 的最小值
//下界:是在每一层的最小r,在给mis miv赋值时解释过了
//其实就是因为第一层的最小r是1,最小h是1
//往下每一层就是各自+1
//注意:(需要的体积-目前的体积)/h的最小值 是为了
//算出r的平方,并且min()是因为两者都有可能超出了
//需要的值(后者超出的时候大概只会在第M层的时候
//出现),而定然也只会有一个超出,所以要取min()
for(int j=min((int)((n-v)/(i*i)),h[k+1]-1);j>=k;j--){
//还是上下界剪枝
//上界:懒得写了
//i是前面的半径
//解释: 前者算出h,后者是上一层的h -1
//下界:k
r[k]=i;//对r的第k层进行赋值
h[k]=j;//对h的第k层进行赋值
//万一这个值“不合格”
//其实 DUCK不必 因为最后总会被覆盖掉的
int temp=0;//底面积临时变量
if(k==1){
temp=r[m]*r[m];//底面积
}
dfs(s+temp+2*i*j,v+i*i*j,k-1);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//先关闭同步流
cin>>n>>m;
mis[0]=0;//虚拟层,第一层顶上的那一层
miv[0]=0;
for(int i=1;i<=m;i++){
//因为第i层的最小r和最小h都是1
mis[i]=mis[i-1]+2*i*i;//其实是侧面积,因为最后只需要加上最底层的底面积就好了
miv[i]=mis[i-1]+i*i*i;//最小体积
}
h[m+1]=1e9+7;
r[m+1]=1e9+7;
//防止最下面的虚拟层第m+1层比第m层小
dfs(0,0,m);
cout<<sum<<'\n';
return 0;
}