题解 P1731 【[NOI1999]生日蛋糕】

### 第一步：预处理 定义 a,b数组，存储第i层最多能用的表面积和体积，便于优化 ### 第二步：深度优先搜索 定义search函数，负责搜索 递归结束条件是： 1：蛋糕已完成，即层数p==m 2：体积超过了预定的值，或者表面积超过了之前存储的最小值ans ## 第三步：寻找优化方案！ 这步尤为重要，没有合适的优化方案会导致超时 ##### 1：对于体积 在第一步已经完成了对最大体积的预处理，所以只需要用当前体积加上b[i-1],判断是否大于了规定体积n即可 即： if(v+b[p-1]>n) return ;//体积超出 ##### 2：对于表面积 如果 当前的表面积+余下的侧面积>当前最优值ans （这个应该很简单证明） 但是，如何实现呢？？？ 于是就有了接下来的公式推理 ~~~ 设已经做了i层蛋糕,则还需做m-i层, Si’：为第i层蛋糕的侧面积, FSi：余下的侧面积 根据定义： V=π*R*R*H（在这里统一删掉π） 则有： 2Vi= 2R[i+1] * R[i+i] * H[i+1] + ...+ 2Rm * Rm * Hm （每一层的体积之和） = R[i+1] * S[i+1]’ + ...+ Rm * Sm’ ≤ R[i+1] * (S[i+1]’+ ...+ Sm’) 放缩法 = R[i+1]*FSi (剩余侧面积) 所以: FSi ≥ 2Vi / Ri+1 ~~~ 因此，剪枝条件变为了 ### 2*(n-v)/r+s>=ans 于是前面预处理的a数组就可以去掉了 第三步完成 ## 综合这三步编写代码，愉快的AC ~~~ #include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[21],b[21],m,n,ans;//a存储表面积,b存储体积 void search(int v,int s,int p,int r,int h)//v为已用体积，s为已有表面积，p为剩余层数，r为半径，h为高 { int i,j,hh; if (p==0)//蛋糕已完成 { if (v==n&&s<ans)//判断是否符合要求并得到更优解 ans=s;//更新最优解 return ; } if(v+b[p-1]>n) return ;//体积超出 //if(s+a[p-1]>ans) return ;//表面积超出 if(2*(n-v)/r+s>=ans) return; //重点：当前的表面积+余下的侧面积>当前最优值 //剩余表面积FS>=2*V剩/r //若FS+s>=ans 则不符合 for(i=r-1;i>=p;i--)//枚举上一层的半径 { if(p==m) s=i*i; hh=min((n-v-b[p-1])/(i*i),h-1); for(j=hh;j>=p;j--)//枚举上一层的高 search(v+i*i*j,s+2*i*j,p-1,i,j); } } int main() { cin>>n>>m; ans=2147483647; a[0]=b[0]=0; for(int i=1;i<21;i++) { //a[i]=a[i-1]+2*i*i;//第i层使用的最大表面积 b[i]=b[i-1]+i*i*i;//第i层使用的最大体积 } search(0,0,m,n+1,n+1); if(ans==2147483647) cout<<'0'; else cout<<ans; return 0; } ~~~