P1731 [NOI1999]生日蛋糕 一本通上也有。
这TM是一道极其简单的深搜剪枝(DP当然可以的了,这里我只讲深搜)。
首先圆柱公式:(有点数学基础都知道)
V=πR2H
S侧=π2RH
S底=πR2
状态描述:
用( i , Ri-1 , Hi-1 , Vi-1 , Si-1 )
i表示打算去做第i层,
已知第i-1层蛋糕的半径和高:Ri-1 ,Hi-1
已知做完第i-1层蛋糕后剩下的蛋糕体积和获得的蛋糕表面积:Vi-1 , Si-1
初始状态:(1,R0,H0,n,0)
目标状态:(m+1,Rm,Hm,0,Sm)
于是,我们要找到一条从初始状态到任意目标状态的路径,并且Sm最小。
扩展的规则:
( i , Ri-1 , Hi-1 , Vi-1 , Si-1 )>>—>>( i+1,Ri,Hi,Vi,Si)
满足:
(1) Ri <Ri-1
(2) Hi <Hi-1
(3) Vi = Vi-1 - Ri* Ri* Hi
(4) Si = Si-1 + 2 * Ri* Hi
基本算法:
dfs ( i , Ri-1 , Hi-1 , Vi-1 , Si-1 )
{
1)如果做好了m层,
如果最终体积为0,刷新最小方案
return;回去再做其他的方案
2)枚举Ri,枚举Hi
Vi = Vi-1 - Ri* Ri* Hi
Si = Si-1 + 2 * Ri* Hi
去做下一层dfs ( i+1 , Ri , Hi, Vi , Si )
}
基本代码:
void Search (int i,int ri, int hi,int si,int vi,int num)
//num:记录上面还有num层没有堆
{
if(i>m)
{ if(vi==)
ans=min(ans,si);
return;
}
for(int r=num;r<=ri-;r++) //每层都比上层小,为整数,最小保证每层增加1
{
if(i==) si=r*r;//把上表面算在第1层
for(int h=num;h<=hi-;h++)
{
Search(i+,r,h,si+*r*h,vi-r*r*h,num-);
}
}
}
^持续更新中……