试题描述

Mr.W 要制作一个体积为 Nπ的 M 层生日蛋糕，每层都是一个圆柱体。 设从下往上数第 i（1≤i≤M） 层蛋糕是半径为 R，高度为 Hi的圆柱。当 i<M 时，要求 Ri>Ri+1且 Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。 令Q=Sπ，请编程对给出的 N和 M ，找出蛋糕的制作方案（适当的 Ri和 Hi的值），使 S最小。（除 Q 外，以上所有数据皆为正整数）

输入

第一行为 N （N≤10000），表示待制作的蛋糕的体积为 Nπ；

第二行为 M （M≤20），表示蛋糕的层数为 M 。

输出

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

输入示例

100

2

输出示例

68

其他说明

附：圆柱相关公式：体积 V=πR^2H；侧面积 A′=2πRH；底面积 A=πR^2。

---

很好玩的一道DFS，跳了一年

主要是平时写代码不注意剪枝，需要用的时候也就没什么思路了

首先是名物额搜索顺序，从下到上

因为是严格递增的，所以给了我们很多优化机会

具体看注释吧

下面给出代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;inline int rd(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0');}int n,m,r[1000],h[1000],maxn=1e9;void dfs(int x,int y,int k){ if(k>=maxn) return ;//如果已经比最优解打了，就不行 if(y==0&&x==m+1){ k+=r[1]*r[1]; if(k
             
              maxn) return ;//如果最小比当前可行最小结果还小就不行 if(y-(r[x-1]*r[x-1]*h[x-1])*(m-x+1)>0) return ;//如果最大都不够总体积，就肯定不行 for(int i=r[x-1]-1;i>=m-x+1;i--){ for(int j=h[x-1]-1;j>=m-x+1;j--){ if(y-i*i*j>=0&&x+1<=m+1){ r[x]=i,h[x]=j; dfs(x+1,y-i*i*j,k+2*i*j); r[x]=h[x]=0; } } } return ;}int main(){ n=rd(); m=rd(); r[0]=h[0]=(int)sqrt(n); dfs(1,n,0); if(maxn==1e9) printf("0"); else write(maxn); return 0;}