冥想盆

?感性理解深搜剪枝（看完這個再看下面的文章）

?理解本題的思路

【代碼實現(xiàn)1:最慢最好理解（自己打的）：100多ms】

【代碼實現(xiàn)2:次慢：30多ms】

【代碼實現(xiàn)3:最快：10多ms】

?最后放上幾個大佬的博客

?

---

【題目描述】

Mr.W 要制作一個體積為?Nπ?的?M?層生日蛋糕，每層都是一個圓柱體。 設(shè)從下往上數(shù)第?i 蛋糕是半徑為 Ri?，高度為 Hi??的圓柱。當(dāng)?i<M時，要求 Ri?>Ri+1?且 Hi?>Hi+1?。由于要在蛋糕上抹奶油，為盡可能節(jié)約經(jīng)費，我們希望蛋糕外表面（最下一層的下底面除外）的面積?Q最小。 令?Q =Sπ ，請編程對給出的?N?和?M?，找出蛋糕的制作方案（適當(dāng)?shù)?Ri??和 Hi??的值），使?S?最小。

（除?Q?外，以上所有數(shù)據(jù)皆為正整數(shù)）

【輸入格式】

?

第一行為?N?，表示待制作的蛋糕的體積為 Nπ；

第二行為?M?，表示蛋糕的層數(shù)為?M?。

【輸出格式】

輸出僅一行，一個整數(shù)?S（若無解則 S=0?）。

【樣例輸入】

100 2

【樣例輸出】

68

【附：圓柱相關(guān)公式：】

體積?

側(cè)面積?

底面積?

【數(shù)據(jù)范圍與提示】

對于全部數(shù)據(jù)，1≤N≤10^4,1≤M≤20。

首先分為四大部分：

1.感性理解深搜和剪枝

2.理解本題思路

3.著重理解代碼的優(yōu)化性

4.最后附上優(yōu)秀的大佬博客?

---

感性理解深搜剪枝（看完這個再看下面的文章）

?接下來，理解本題的思路

不得不承認，我覺得最麻煩的就是這個半徑和高的最小值，這個就要理解好題目。題目中說半徑如此，高也是如此,，這意味著什么？意味著底下每一層的半徑和高度至少比上一層多1，也就是說，最底下那一層的半徑和高最小為m。

有了這一步，我們的半徑和高的規(guī)律已經(jīng)心中有數(shù)了，也知道應(yīng)該怎樣了，那么我們在主函數(shù)中的初始化應(yīng)該是怎樣的呢？

1.for(int i=m;i*i*m<=n;i++) //這個i表示的是半徑的范圍2.for(int j=m;i*i*j<=n;j++) //這個j表示的是高的范圍3.if(i*i+2*i*j<minn) //這一步表示的是只有我們在枚舉到這個表面積小于我們之前記錄過的才可以繼續(xù)4.dfs(1,i*i*j,i*i+2*i*j,i,j) //進入遞歸函數(shù)， /* 1.從前1層開始 2.體積為i*i*j 3.表面積為2*i*j 4.i表示半徑 5.j表示高 */

?萬事開頭難，慢慢理解題目就好了

我都以這個最慢的代碼為基準，因為我最熟悉這個，然后其他的幾個代碼，把最慢的理解清楚之后，理解起來很簡單，而且我都注釋的很清楚了，所以不用慌。

接下來進入遞歸當(dāng)中，遞歸當(dāng)中最重要的莫過于剪枝了（我會放出三個代碼，分別是最慢最好理解，次慢次理解，最快難理解），這三個代碼剪枝的方法不一樣，但始終是三個方面

1.前d層的體積加上后面體積的最小值還大于n（題目給出的體積的限制）就剪枝

2.前d層的體積加上后面體積的最大值還小于n，就剪枝

3.前d層的表面積加上后面的表面積大于我們記錄過的最優(yōu)解，剪枝（沒有這一步，再多的剪枝都會超時，這個是最重要的剪枝也是最難的剪枝，而且最坑的是，就算你用數(shù)組來記錄也沒用，這是一條公式，一條極難想到的公式）

接下來我們一個一個理解啊

1.體積剪枝（最大值不足以滿足題目要求） if(v+(r-1)*(r-1)*(h-1)*(m-d)<n)return; /*1.如果當(dāng)前體積加上之后每層的最大值,還比題目要求的體積小，直接結(jié)束該趟遞歸2.我在主函數(shù)當(dāng)中講了我們的搜索是自下而上，所以下面一層的高和半徑都比上面一層要大3.為什么說是最大值呢？因為我們選取的是當(dāng)前上一層的半徑，而且越往上越小而我們乘以的同樣也是那么多層，所以說這個是最大值 */ 2.體積剪枝（最小值超過題目要求） if(v+m-d>n)return; /*1.如果當(dāng)前體積加上之后每層的最小值,還比題目要求的體積大，直接結(jié)束該趟遞歸2.為什么說是最小值呢？因為我們的上一層的高和半徑是比下面的那一層要小的，也就是最頂上的可能半徑就為1，是最小的，既然是最小的說明下面的就比他要大，但是我們就直接最小半徑的平方1*1*(m-d)也就是層數(shù)，那么可能會疑惑高去哪里了？高也是假設(shè)了最小的1，所以整個半徑平方乘以高乘以層數(shù)=1*1*1*(m-d)=m-d */3.最優(yōu)性剪枝（剪掉超過最優(yōu)解的） if(2*(n-v)/r+s>=minn)return; 不要著急這個我要慢慢給你們證明

我們來感性證明一下最優(yōu)性剪枝啊

?首先我們分成幾部分

第一部分：n-v

第二部分：minn

第三部分：除以r乘以2

第四部分：全部一起

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 第一部分：v

無論如何這個都是可以理解的，v代表前d層的體積，然后我們就是把這個蛋糕一層一層的體積相加就等于總體積

那么

這個就是剩下部分的體積，可以理解的吧

第二部分：minn

過了很久我終于又開始完善這個博客了。

這個minn可能是比較難理解的，那么我們一步步來

這個的值是小于?

?為什么呢？因為這個r是我們記錄的最開始的這個最底層的這個的半徑，這個半徑是所有半徑當(dāng)中最大的，所以每一次都這么計算的值是最大的，那么我們不難想到，既然原本是要小于的，只要這個值大于的話，是不是就可以剪枝？那么我們把這個式子所有的 r 提出來合并，就變成了??

第三部分：除以r乘以2

這樣看可能沒有感覺，我們只看中間的那一串，h[1]*r[1]一直加到h[d]*r[d]，然而我們的這個側(cè)面積的公式就是2hd，所以我們就要進行一個小修改，變成,這個就是我們之前辛辛苦苦記錄過的前d層的表面積，也就是我們所更新過的minn值，就是到當(dāng)前為止記錄過的最小的表面積的值

第四部分：全部一起

好，我在上面說了如果我們找到的這個大于就要剪枝的對吧，那么我們也說了上面的小修改，我們先列出一個原不等式啊：

這個是我們的剪枝條件，但是因為這個的值就是我們之間已經(jīng)找到了的v的值，所以我們直接用v來代替，然后剩下了就是 n-v=是吧，這個時候我們就要把這個和之前我們修改過的放在一個，兩邊同時除以這個r乘以2就變成了，這個是最終形式，s其實就是我們前d層的體積所對應(yīng)的表面積，那么這個是什么意思呢？就是說這個這個是任何一個體積的共同形式，那么我們除以了r再乘以2之后就變成了什么呢，變成了就是我們熟悉的側(cè)面積，這個代表的是我們剩余體積的側(cè)面積，加上我們之前的這個s就是全部的表面積，這個的計算結(jié)果是不能大于我們之前記錄過的這個minn的值，所以的話，這個就成為了我們最重要的剪枝了

所有的剪枝我都講清楚了對吧，接下來就看代碼實現(xiàn)吧?

【代碼實現(xiàn)1:最慢最好理解（自己打的）：100多ms】

?

/* 題目解釋： 題目的意思：有一個體積為Nπ的M層蛋糕，底下每一層的高度和半徑至少比上一層的大1， 也就是說，最底下一次的半徑和高度至少為M了。(關(guān)鍵關(guān)鍵) 求解符合題意，又要求其表面積要最小的蛋糕，求出其表面積最小值為多少。 依次遞歸用DPS去尋找符合體積大小的數(shù)據(jù)，求解找到的最小值便是答案 */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,minn=2e+9; //min表為面積最小的值，初始化為一個極大值 void dfs(int d,int v,int s,int r,int h) //前d層蛋糕體積為v 表面積為s 第d層半徑r 高度h {if(d==m)//前d層就是m層，表示我們已經(jīng)搜索完了 {if(v==n)minn=s;//如果體積也符合題目要求的話，更新表面積的最小值 return;//返回值 }if(v+(r-1)*(r-1)*(h-1)*(m-d)<n)return;/*1.如果當(dāng)前體積加上之后每層的最大值,還比題目要求的體積小，直接結(jié)束該趟遞歸2.我在主函數(shù)當(dāng)中講了我們的搜索是自下而上，所以下面一層比上面一層要小3.為什么說是最大值呢？因為我們選取的是當(dāng)前上一層的半徑，而且越往上越小而我們乘以的同樣也是那么多層，所以說這個是最大值*/ if(v+m-d>n)return; /*1.如果當(dāng)前體積加上之后每層的最小值,還比題目要求的體積大，直接結(jié)束該趟遞歸2.為什么說是最小值呢？因為我們的上一層是比下面的那一層要小的，也就是最頂上的可能半徑就為1，是最小的，既然是最小的說明下面的就比他要大，但是我們就直接最小半徑的平方1*1*(m-d)也就是層數(shù)，那么可能會疑惑高去哪里了？高也是假設(shè)了最小的1，所以整個半徑平方乘以高乘以層數(shù)=1*1*1*(m-d)=m-d*/if(2*(n-v)/r+s>=minn)return; /*如果求解過程半途找到比當(dāng)前最小值，也就是minn的值還大的數(shù)據(jù)，結(jié)束該趟遞歸這一步是最關(guān)鍵的一步但是我不知道現(xiàn)在在這里怎么表示出來 */ for(int i=r-1;i>=m-d;i--)/*i(半徑)[再上一層的半徑]的最小值要保證大于當(dāng)前這一層半徑的最小值題目解釋當(dāng)中說的至少要大1，也就是說上一層的半徑最大是當(dāng)前這一層的半徑-1也就是r-1最小的話就是也要大于等于剩下的層數(shù)，不然后面的層就沒有整數(shù)半徑比如說：總共有5層，當(dāng)前是第3層(順數(shù))，第3層的半徑是5,那么第2層的半徑最大就是4，最小的話就是（5-3）=2因為只有大于等于2的時候，這一層的上一層才有半徑，如果第2層的半徑是1的話，那么至少要大于等于1，也就是第1層的半徑小于等于0這個顯然是不可能的 */{for(int j=h-1;j>=m-d;j--)/*j(高度)[再上一層的高度]的最小值要保證大于當(dāng)前這一層高度的最小值跟半徑是同樣的道理，這里就不再解釋了 */ {if((i*i*j+v<=n)&&(s+2*i*j<minn))/*如果我們后面找到的這個半徑和高度組合的體積小于等于n*//*并且它的面積比我們之前記錄過的要小的話*/dfs(d+1,v+i*i*j,s+2*i*j,i,j);/*遞歸搜索子狀態(tài)，也就是處理下一個*/ }} } int main() {scanf("%d%d",&n,&m);for(int i=m;i*i*m<=n;i++)/*1.i表示半徑，半徑的平方(也就是底面積)*層數(shù)(也就是體積)小于要求的體積的話，可以繼續(xù)2.i從m開始是因為，底下每一層的高度和半徑至少比上一層的大1，也就是說，最底下一次的半徑和高度至少為M了*/{for(int j=m;i*i*j<=n;j++)/*1.j表示高度，高度乘以底面積小于要求體積，可以繼續(xù)2.i從m開始是因為，底下每一層的高度和半徑至少比上一層的大1，也就是說，最底下一次的半徑和高度至少為M了 */ {if(i*i+2*i*j<minn)/*小于我們一直更新的最小值，才傳入*/ dfs(1,i*i*j,i*i+2*i*j,i,j);/*從第m層開始，我們之前的枚舉是自下而上，所以在搜索中也是自下而上注意：(分開五個來分析) (1)從前1層開始 (2)體積是半徑*半徑*高 (3)表面積不單單是側(cè)面積，最底下那一層的表面積 (4)i表示半徑(5)j表示高度 */ }}printf("%d\n",minn);/*輸出最小值*/return 0; } /* 體積V=πR*R*H 側(cè)面積A’=2*π*R*H 底面積A=π*R*R */

這個代碼為什么會最慢了，因為我們沒有用數(shù)組，也就是說，沒有我們之前的這個記憶化剪枝技巧

【代碼實現(xiàn)2:次慢：30多ms】

#include<cstdio> #include<cstring> #include<algorithm> #define oo 1000000000 using namespace std; int ans; int minn[20];//存儲體積 int n,m; void dfs(int k,int r,int h,int s,int v) //k：當(dāng)前層數(shù) r：當(dāng)前層的半徑 h：高度 s：表面積 v：剩下的體積 {if (s+2*v/r>ans) return;//我們知道剩余的體積，能不能根據(jù)體積，估算一個剩余的側(cè)面積，//如果（ 當(dāng)前的表面積+余下的側(cè)面積的最小值）//比最優(yōu)值還大，那么當(dāng)前層的搜索就沒有意義。if (v-minn[m-k]<0) return;//如果剩余的體積減去后面要用的體積小于0的話，說明不夠體積做一個蛋糕 if (k==m)//邊界情況 {if(v==0) if(s<ans) ans=s;return;}for(int tr=r-1;tr>=m-k;tr--)for(int th=h-1;th>=m-k;th--)//不斷縮小半徑和高度 進行枚舉(跟那個的意思是一樣的) {int ts,tv;ts=s+2*tr*th;//后面的表面積 tv=v-tr*tr*th;//剩下的體積 dfs(k+1,tr,th,ts,tv);//搜索下一個 } } int main() {scanf("%d%d",&n,&m);ans=oo;int j=1;//最小的高為只能為1 for(int i=1;i<=m;i++)//預(yù)處理一個數(shù)組將最小的存起來 等會剪枝 {minn[i]+=i*i*j;//記錄體積 j++;//高會增加，題目中說了 }for(int r=m;r*r*m<=n;r++)//因為半徑是越來越小的 所以r的大致范圍可以確定 for(int h=n/(r*r);h>=m;h--)//高度的大致范圍也可以確定 {int s,v;//表面積和剩下的體積 s=r*r+2*r*h;//第一層的側(cè)面積+總頂面積（可以通過平移使所有頂面積拼成第一層的頂面積） v=n-r*r*h;dfs(1,r,h,s,v);} if(ans==oo) ans=0;//不可能這么大，所以就是沒有體積炸掉了 printf("%d\n",ans);return 0; }

這個用了記憶化，但是仍然慢的主要原因應(yīng)該是這個代碼的很多表達方式不是最簡單，讓電腦運行次數(shù)最少最方便的

【代碼實現(xiàn)3:最快：10多ms】

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,minv[21],mins[21]; //V=n*pi m 層數(shù) 自頂向下1.2.3...m //minv[i]表示i層到0層加起來的最小總體積 minvs 最小表面積 const int inf=1000000000; // inf 足夠大就可以 int(32) -2^31~2^31-1=2147483647 int best=inf; //best 最小表面積 void dfs(int depth,int sumv,int sums,int r,int h)//深度優(yōu)先搜索 自底m向上搜索 //depth表示剩余層數(shù)r h表示當(dāng)前層得半徑和高度 sumv已經(jīng)用的總體積 sums已經(jīng)生成的總表面積 {if(depth==0){if(sumv==n&&sums<best)//搜索完成 更新最小表面積best{best=sums;}return;}// 三個剪枝條件：//1、已經(jīng)搜索過的體積加上還未搜索過的最小體積不能比總體積n 大//2、已經(jīng)搜索過的表面積加上還未搜索過的最小表面積不能比之前的最小總表面積best大 //3、n-sumv既所剩體積記作dv 還需要的表面積為s//s=2*ri*hi+2*r(i-1)*h(i-1)+... >=2*ri*hi*ri/r+2*r(i-1)*h(i-1)*r(i-1)/r+...// =2*dv/r（i從depth-1取,r為當(dāng)前半徑 ri/r<1）// 所以得到還需要的最小表面積s=2*(n-sumv)/r，//如果最小的s和已經(jīng)搜索過的表面積sums依然比best大 就不用繼續(xù)搜索了if(sumv+minv[depth-1]>n||sums+mins[depth-1]>best)//剪枝如上所述return;for( int i=r-1;i>=depth;i--)//遞減順序枚舉depth層半徑的每一個可能值,這里第depth層的半徑最小值為depth{if(depth==m)sums=i*i; //俯視蛋糕底面積作為外表面積的初始值(總的上表面積,以后只需計算側(cè)面積)int maxh=min((n-sumv-minv[depth-1])/(i*i),h-1); //maxh最大高度,即depth層蛋糕高度的上限,//(n-sumv-minv[dep-1])表示第depth層最大的體積for(int j=maxh;j>=depth;j--) //同理,第depth層的最小高度值為depth{dfs(depth-1,sumv+i*i*j,sums+2*i*j,i,j);//遞歸搜索子狀態(tài)}} } int main() {scanf("%d%d",&n,&m); int rmax=sqrt(n); //rmax初始半徑 底層半徑 最大值為sqrt(n)int hmax=n; //hmax初始高度 高度最大為 nminv[0]=mins[0]=0;for(int i=1;i<=m;i++)//初始化minv和mins數(shù)組{ minv[i]=minv[i-1]+i*i*i; //從頂層(即第1層)到第i層的最小體積//minv[i]成立時第j層的半徑和高度都為jmins[i]=mins[i-1]+2*i*i;}dfs(m,0,0,rmax,hmax);//dfs(m,0,0,n+1,n+1);if(best==inf)best=0; //無解if(best==0)printf("0\n"); else printf("%d\n",best); return 0; }

最快的，用了記憶化，而且所有的表達方式也是為了后面更方便而定義的

最后放上幾個大佬的博客，感謝這些大佬

博客1??博客2?博客3?博客4?博客5?博客6?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的#10019. 「一本通 1.3 例 2」生日蛋糕的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。