C++ 洛谷 P1731 [NOI1999]生日蛋糕

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-);
}
}
}

^持续更新中……

上一篇:Go的sort接口实现


下一篇:数据库获取前N条记录SQL Server与SQLite的区别