P1731的生日蛋糕是哪一款？

本文共计597个文字，预计阅读时间需要3分钟。

这道题显然是1999年省选题！可能是洛谷蓝题里最水的了。题目链接：https://www.luogu.com.cn/problem/P1731。大家有兴趣可以去看看。题目描述：就是类似这样一个蛋糕：现在给它体积和层数。

这道题居然是1999年省选题！这可能是洛谷蓝题里最水的了。。。

题目链接：www.luogu.com.cn/problem/P1731　　大家有兴趣可以去看看

题目描述：就是类似这样一个蛋糕：

现在给它体积和层数，为了省奶油，要求它最小表面积（不算底面）

题目思路：深搜剪枝，从下到上枚举每层的半径和高，最终求出最小表面积（具体思路和剪枝详见代码注释）

代码：

#include<bits/stdc++.h> using namespace std; int r[21],h[21],n,m,we=0x3f3f3f3f;//定义数组存储半径和高是为了省事 void dfs(int v,int s,int k,int p){//v：体积；s：表面积；k和p：层数（一个倒着的一个正着的） int i,j; //下面是剪枝，可以最后看 if(v<0){//体积超了 return;//返 } if(k<0){//层数超了 return;//返 } if(s+k+r[1]*r[1]>we){//表面积超了当前最小值，再往下搜没意义了 return;//返 } if(v>r[p-1]*r[p-1]*h[p-1]*k){//假设之后的体积全=当前体积，还是不够 return;//返 } //剪枝结束 if(k==0&&v==0){//满足条件 s+=r[1]*r[1];//加上最下面的底面积（=所有层有用的底面积） we=min(we,s);//取最小值 return; } for(i=r[p-1]-1;i>=k;i--){//枚举半径（i的初始值是上一层-1） for(j=h[p-1]-1;j>=k;j--){//枚举高 if(v>=i*i*j&&k>=0){ r[p]=i; h[p]=j; dfs(v-i*i*j,s+2*i*j,k-1,p+1);//v减去当前层体积，s加上侧面积 r[p]=i;//回溯 h[p]=j; } } } } int main(){ cin>>n>>m; h[0]=int(sqrt(n)); r[0]=int(sqrt(n));//手动确定最底层高和半径的最大值 dfs(n,0,m,1); if(we==0x3f3f3f3f){//若值不变 cout<<0;//输出0 }else{ cout<<we; } return 0; }