学步园

Description

Input

Output

Sample Input

100


2

Sample Output

68

Hint

#include <iostream><br /> #define in(a,b) (a<b?a:b)<br /> using namespace std;<br /> int n,m;<br /> int minv[21],mins[21];<br /> int best = 65535;//默认取值，尽可能大<br /> void solution(int v,int s,int floor,int r,int h)<br /> {<br /> if(floor==0)<br /> {<br /> if(v==n && s<best)<br /> best=s;<br /> return ;//判断返回条件后，无论是否满足最优解判断，都返回<br /> }<br /> if(v+minv[floor-1]>n || s+mins[floor-1]>best || 2*(n-v)/r+s>best)<br /> return ;//第一轮剪枝，分别判断当前v加上最小可能性的minv，当前s加上最小可能性的mins，第三个判断条件的推导是：<br /> //剩余体积，/半径r，剩余 r*h,之后由于侧面积:2*r*h，故可得此结论。即假设剩余的体积作用，得到尽可能小的结果<br /> int i,j,hh;<br /> if(floor==m)<br /> s=(r-1)*(r-1);<br /> for(i=r-1;i>=floor;i--)//第一层判断，逐级向下取数，注意其中最小取到floor，以减小循环次数<br /> {<br /> hh=in((n-v)/(i*i),h-1);//判断，在同样的情况下，满足体积关系，找到最小的解值最为高，向下取值<br /> for(j=hh;j>=floor;j--)//原理同上<br /> solution(v+i*i*j,s+2*i*j,floor-1,i,j);<br /> }<br /> }<br /> int main()<br /> {<br /> int i;<br /> minv[0]=0;<br /> mins[0]=1;//第一层最小可能的面积<br /> for(i=1;i<=20;i++)<br /> {<br /> minv[i]=minv[i-1]+i*i*i;<br /> mins[i]=mins[i-1]+2*i*i;<br /> }<br /> cin>>n>>m;<br /> solution(0,0,m,n+1,n+1);<br /> if(best==65535)<br /> {<br /> cout<<0<<endl;<br /> }<br /> else<br /> {<br /> cout<<best<<endl;<br /> }<br /> return 0;<br /> } 

以上是我对代码的解释，不过还有继续剪枝的余地，以上只进行了5次。