题解 P1731 【生日蛋糕】

yyyxy · 2017-06-07 08:20:41 · 题解

搜索加剪枝

#include<iostream>
#include<cmath>
using namespace std;
int m,n,Minv[21],Best;
void Read()
{  int i;
   cin>>n>>m;
   Minv[0]=0;
   for(i=1;i<=m;i++)Minv[i]=Minv[i-1]+i*i*i;  //初始化最小体积和
}
void search(int floor,int r,int h,int s,int v)//对每层蛋糕进行搜索
{  int i,j,Maxv;
   if(floor==0&&v==0){if(s<Best)Best=s;return;}
   if(s+2*v/r>=Best)return;//剪枝1,最优性剪枝
   if(v<Minv[floor])return;//剪枝2,根据下界进行可行性剪枝
   Maxv=0;
   for(i=floor;i>=1;i--)Maxv+=(r-i)*(r-i)*(h-i);//最大方式做蛋糕
   if(Maxv<v)return; //剪枝3,根据上界进行可行性剪枝
   for(i=r-1;i>=floor;i--) //枚举floor层蛋糕的半径
      for(j=h-1;j>=floor;j--) //枚举floor层蛋糕的高度
         search(floor-1,i,j,s+2*i*j,v-i*i*j);
}
int main()
{  int r,h,s,v;
   Read();
   Best=0x7fffffff/2;
   for(r=m;r<=sqrt(n);r++)//枚举最底层蛋糕的半径
      for(h=n/(r*r);h>=m;h--)//枚举最底层蛋糕的对应高度
      {  s=r*r+2*r*h;
         v=n-r*r*h;
         search(m-1,r,h,s,v);
      }   
   cout<<Best<<endl;
}