「一本通 1.3 例 2」生日蛋糕

题目

提目描述

$Mr.W$要制作一个体积为$N\pi$的$M$层生日蛋糕，每层都是一个圆柱体。

设从下往上数的第$i$层蛋糕的半径为$R_i$，高度为$H_i$的圆柱。当$i<M$时，要求$R_i>R_{i+1}$且$H_i>H_{i+1}$。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积$Q$最小。

令$Q=S\pi$,请编程对给出的$N$和$M$，找出蛋糕的制作方案（适当的$R_i$和$H_i$的值),使$S$最小。

（除$Q$外以上数据皆为正整数）

输入格式

第一行为$N$,表示待制作的蛋糕的体积为$N\pi$

第二行为$M$,表示带制作的蛋糕层数为$M$。

输出格式

输出仅一行，一个整数$S$（若无解则$S=0$）。

样例

输入

100

2

输出

68

**附：**圆柱相关公式：

? 体积：$V=\pi R^{2}H$

? 侧面积：$S^{\prime }=2\pi RH$

? 底面积：$S=\pi R^2$

数据范围与提示

对于全部数据：$1\le N\le 10^4,1\le M\le 20$

分析

**搜索框架:**从下往上搜索，枚举搜索面对的状态有：正在搜索蛋糕第$dep$层，当前外表面面积$s$，当前体积$v$,第$dep+1$的半径和高度。

整个蛋糕的“上表面”面积之和等于最底层的面积，可以在第$M$层直接累加到$s$中。这样在$M?1$层的搜索中，只需要计算侧面积。

由于从蛋糕的第二层开始，底面半径和高度要大于上面的蛋糕，极限思想：假设蛋糕只有一层则这层的底面半径最大值为：$\sqrt{n}$,假设每层蛋糕的半径都为1，则蛋糕的高度最大为n，之后对于每次搜索都进行三次剪枝：

1. 当前的体积加上剩余层数的最小值大于总体积
2. 当前的表面积加上剩余层的表面积最小值大于以求得的最小表面积
3. 当前的体积大于$n$

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000000000
#define maxx 100
int n,m;
int minv[maxx];
int mins[maxx];
int maxh,maxr;
int ans=maxn;
void dfs(int dep,int v,int s,int r,int h){
    //剩余层数，已用体积，已生成的面积，当前层的半径，当前层的高度if(dep==0){
    if(v==n&&s<ans){
    ans=s;} return ;} if(v>n)return ;if(v+minv[dep-1]>n)return ;if(s+mins[dep-1]>ans)return ;if(2*(n-v)/r+s>=ans)return ;for(int i=r-1;i>=dep;i--){
    if(dep==m)s=i*i;//底面积 int hh=min((n-v-minv[dep-1])/(i*i),h-1);//计算dep层蛋糕的高度上限，n-s-minv[dep-1]为dep层的最大高度 for(int j=hh;j>=dep;j--){
    dfs(dep-1,v+i*i*j,s+2*i*j,i,j);}}
}
int main(){
    scanf("%d%d",&n,&m);maxr=sqrt(n);maxh=n;minv[0]=mins[0]=0;for(int i=1;i<=m;i++){
    minv[i]=minv[i-1]+i*i*i;mins[i]=mins[i-1]+2*i*i;}dfs(m,0,0,maxr,maxh);if(ans==maxn)printf("0");else printf("%d",ans);return 0; 
}