前言：這是算法中很經典的一道題
題目：7月17日是Mr.W的生日，ACM-THU為此要制作一個體積為NπNπ的M層生日蛋糕，每層都是一個圓柱體。
設從下往上數第i層蛋糕是半徑為RiRi, 高度為HiHi的圓柱。
當i < M時，要求RiRi > RiRi+1且HiHi > HiHi+1。
由于要在蛋糕上抹奶油，為盡可能節約經費，我們希望蛋糕外表面(最下一層的下底面除外)的面積Q最小。
令Q = Sπ ，請程式設計對給出的N和M，找出蛋糕的制作方案(适當的RiRi和HiHi的值)，使S最小。
除Q外，以上所有資料皆為正整數 。
輸入格式
輸入包含兩行，第一行為整數N(N <= 10000)，表示待制作的蛋糕的體積為NπNπ。
第二行為整數M(M <= 20)，表示蛋糕的層數為M。
輸出格式
輸出僅一行，是一個正整數S(若無解則S = 0)。
資料範圍
1≤N≤100001≤N≤10000,
1≤M≤201≤M≤20
輸入樣例：
100
2
輸出樣例：
68
題解思路：
該題是經典的爆搜剪枝問題，要求體積不變下，表面積最小(除了第一層的底面積) ，那麼從每一層蛋糕的角度來看，蛋糕的半徑和高度都是單調遞減，從枚舉每一層的半徑和高度，枚舉的時候有一個原則，即優先枚舉 選擇決策少的來擴充，半徑和高度這兩個變量搜尋範圍的确定有點意思，後面會講解。
關于爆搜剪枝問題，剪枝當然是重中之重，該題可以提出四個剪枝方法；剪枝經常應用于深搜和廣搜當中，政策就是尋找過濾條件，提前減少不必要的搜尋路徑。
搜尋解的讨論(搜尋極其重視搜尋順序，個頭大的先搜尋，方案數将較少)：1、貪心的思想是保持每步最優解，以達到全局最優解2、爆搜如何産生最優解呢？将需要搜尋順序排成從大到小，從中進行搜尋。
從蛋糕從下往上搜尋，上表面積就是最下面圓的面積，求解過程注重側面積和體積即可，
假設目前狀态有 s,v,rdep+1∼m,hdep+1∼ms,v,rdep+1∼m,hdep+1∼m， dep對應的狀态，有：
n−v≥r2dephdep
n−v≥rdep2hdep
有上界：
rdep=min(n−v,rdep+1−1)
rdep=min(n−v,rdep+1−1)
hdep=min(n−vr2dep,hdep+1−1)
hdep=min(n−vrdep2,hdep+1−1)
有下界：
rdep=dep,hdep=dep
rdep=dep,hdep=dep
很明顯，ri=i,hi=iri=i,hi=i 是最小的情況，
它們對應的 minsi=2rihi=2i2,minvi=r2ihi=i3minsi=2rihi=2i2,minvi=ri2hi=i3
如果目前結果加最小情況超過答案，那麼後面就不會有解。
在有解的情況下，有下面不等式成立：
s1∼dep−1=2∑i=1dep−1rihi,v1∼dep−1=n−v=∑i=1dep−1r2ihi
s1∼dep−1=2∑i=1dep−1rihi,v1∼dep−1=n−v=∑i=1dep−1ri2hi
ri
ri
s1∼dep−1=2∑i=1dep−1rihi=2rdep∑i=1dep−1rihirdep≥2rdep∑i=1dep−1r2ihi
s1∼dep−1=2∑i=1dep−1rihi=2rdep∑i=1dep−1rihirdep≥2rdep∑i=1dep−1ri2hi
s1∼dep−1≥2(n−v)rdep
s1∼dep−1≥2(n−v)rdep
即，2(n−v)rdep2(n−v)rdep 是後面未求面積的下限，如果 2(n−v)rdep+s2(n−v)rdep+s 大于答案，那麼這樣的狀态是不會更優的。
作者：VMice
連結：https://www.acwing.com/solution/AcWing/content/1500/
#include
#include
#include
using namespace std;
const int N=25,Inf=1e9;
//全局變量
int n,m;
int R[N],H[N];//每層的半徑和高度
int minv[N],mins[N];
int res=Inf ; //定義初始答案為正無窮
void dfs(int u,int v,int s)//args:目前層數、目前體積、目前表面積
{
//四個剪枝方法
if(v+minv[u]>n)return;
if(s+mins[u]>=res)return;
//最重要的優化
if(s+2*(n-v)/R[u+1]>=res)return;
if(!u) //如果到達最上一層，輸出最上一層，非常重要的一個語句，目的是使爆搜達到條件後終止
{
if(n==v)res=s;//在最後一層搜尋時，主要的操作步驟是找到滿足條件的解後結束
return;
}
//終于了解了為什麼第u層的r,h最小半徑為u,因為最頂層r,h最小為1,那麼依次遞增，最大層的m的r,h最小值為m
for(int r=min((int)(double)sqrt(n-v),R[u+1]-1);r>=u;r–)//枚舉狀态，r,h從大到小枚舉，同時有範圍
for(int h=min((n-v)/r/r,H[u+1]-1);h>=u;h–) //
{
//注意當最後一層确定時，要加第一層的低盤面積
int t=0;
if(u==m)t=r*r;
R[u]=r,H[u]=h; //新知識點：更新目前的半徑和高度
dfs(u-1,v+r*r*h,s+2*r*h+t);//參數更新及傳遞
}
}
int main()
{
//讀入資料
cin>>n>>m;
//初始化minv,mins
for(int i=1;i<=m;i++)
{
// minv[i+1]=minv[i]+i*i*i;
//mins[i+1]=minv[i]+2*i*i;
minv[i]=minv[i-1]+i*i*i;
mins[i]=mins[i-1]+2*i*i;
}
//處理搜尋邊界#這裡設定哨兵，幫助完成邊界
R[m+1]=H[m+1]=Inf;//?
dfs(m,0,0);//賦初值最底下一層，初始面積為0，初始表面積為0
cout<
for(int i=0;i
{
cout<
cout<
cout<
}
return 0;
}