poj1190，DFS/已知一个等式，求另一个最小值

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。

令Q = Sπ

请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。

（除Q外，以上所有数据皆为正整数）

Input

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

Output

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

已知n=r1^2*h1+....ri^2*hi+....rm^2*hm(n,m已知，所有数为正整数)，求s=r1^2+2*r1*h1+....2*ri*hi+...+2*rm*hm最小值。

DFS爆搜，+剪枝。关键是怎么减的问题，归纳如下：1，从第一个已知的减，如缩小范围，超过等，2.从目前最优的情况考虑，如果已经比目前最优差了，就不用考虑下去了！

关键剪枝说明：“假设只有一个圆柱，该圆柱的半径为r,体积为V，那么根据体积和表面积公式，可知：2 * v/r 是该圆柱的侧面积。现在我们有2个圆柱，要求这两个圆柱叠在一起之后满足题目的条件：下柱半径>上柱半径。现在把上柱往下压扁，压到和下柱的半径相等，那么根据表面积和体积公式，我们知道上柱的侧面积会减小。（s=2
* v/r,相同体积时，R大，侧面积小）所以多个圆柱叠立，假设最下面圆柱半径最大，该半径为r。于是，这些圆柱的侧面积之和>=等体积的半径为r的圆柱的侧面积。

#include<iostream>

#include<cmath>

using namespace std;

int r[21];int h[21];

int ans;

void dfs(int cur,int m,int n,int sum,int sum_ans)

{

   if(cur==m+1)                  //注意点！先后问题！

   {

       if(sum==n)

       {

            if(sum_ans<ans)ans=sum_ans;

       }

   }

   else

   {

      for(int i=m-cur+1;i<r[cur-1];i++)

        for(int j=m-cur+1;j<h[cur-1];j++)

        {

            r[cur]=i;

            h[cur]=j;

           // cout<<i<<"**"<<j<<endl;

             int temp=m-cur;

            if(sum+i*i*j+(m-cur)*r[cur]*h[cur]*r[cur]<n)continue; //体积不可能到N了。注意continue,与break 区别

            if(sum+i*i*j>n)break;                              //体积已经大于n了。

            if(sum_ans+2*i*j+2*(n-sum-i*i*j)/i>ans)break;     //关键剪枝！把剩余体积全转化为表面积（按最大的转是表面积最小的情况）

            if(sum_ans+2*i*j+(temp*(temp+1)*(2*temp+1)/3)>ans)break;

                                     //  这样写不可，一次return后，这次不再还原。 sum+=i*i*j;

                                       //   if(sum>n) return ;

        dfs(cur+1,m,n,sum+i*i*j,cur==1?sum_ans+2*i*j+i*i:sum_ans+2*i*j);        //非也，把这层RETURN了，这层有些值还是可以的，下次循环

                                         //   sum-=i*i*j;

        }

   }

}

int main()

{

  int n,s,m;

  cin>>n>>m;

      ans=1000000;

      r[0]=(n-m*(m-1)*(2*m-1)/6)/m;

      h[0]=(n-m*(m-1)*(2*m-1)/6)/(m*m)+1;

      dfs(1,m,n,0,0);

      if(ans==1000000)cout<<0<<endl;

      else cout<<ans<<endl;

return 0;

}

巴特西

poj1190，DFS/已知一个等式，求另一个最小值

最新文章

热门文章