AcWing 168. 生日蛋糕 python 注释
原题链接
中等
作者:
思念聚成海
,
2021-12-16 20:53:04
,
所有人可见
,
阅读 469
推导难,但代码相对还是比较好写的
V = int(input())
n = int(input())
R = [0]*(n+2); H = [0]*(n+2)
# 哨兵 防止边界条件,比如第n层会用到第n+1的
R[n+1] = H[n+1] = float('inf')
minv = [0]*(n+1); mins = [0]*(n+1)
ans = float('inf')
# 预处理前i层的最小体积和侧面积
for i in range(1,n+1):
minv[i] = minv[i-1] + i*i*i
mins[i] = mins[i-1] + 2*i*i
# u: 当前蛋糕的层数;v: 当前累计的体积;s: 当前累计的侧面积
def dfs(u,v,s):
global ans
# 合法性剪枝
if v + minv[u] > V: return
# 最优性剪枝
if s + mins[u] >= ans: return
if s + 2*(V-v) / R[u+1] >= ans: return
# 搜索完毕还需要判断体积是否相等,相等才更新答案,结束
if u == 0:
if v == V: ans = s
return
# 从大到小枚举半径和高度
temp = V - v - minv[u-1]
for r in range(min(R[u+1]-1,int((temp / u)**0.5)),u-1,-1):
for h in range(min(H[u+1]-1,int(temp / (r*r))),u-1,-1):
R[u],H[u] = r,h
# 最后一层要加上底面积
if u == n:
dfs(u-1,v + r*r*h,s + 2*r*h + r*r)
else:
dfs(u-1,v + r*r*h,s + 2*r*h)
# 从大的方向开始搜索,也就是最后一层开始
dfs(n,0,0)
print(ans) if ans < float('inf') else print(0)