T01190: 生日蛋糕

http://cs101.openjudge.cn/practice/01190/

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q = Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）

输入

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

输出

仅一行，是一个正整数S（若无解则S = 0）。

样例输入

100
2

样例输出

提示

圆柱公式体积V = πR2H 侧面积A' = 2πRH 底面积A = πR2

来源

Noi 99

【陈子良 25物理学院】让你看看什么是地表最强剪枝：

设dfs(i,n,s)表示当前处于蛋糕第i层，已使用体积为n，当前表面积为s的状态。其中i从蛋糕顶部到底部分别记为0到M-1，这样对于第i层蛋糕，其上方的蛋糕层数就是i。这是为了后面计算的方便。用单调栈Rstack和hstack分别记录各层蛋糕的半径和高度。

本题的剪枝主要有两个来源。一个是R和h均为正整数，且随蛋糕层数增加而严格单调递减；一个是蛋糕总体积为N。

对于蛋糕的第i层，首先其上方的蛋糕都应存在，从顶向下其半径和高度最小应分别是[1,2,3···i]，因此

R \geq i + 1, h \geq i + 1

当前蛋糕半径和高度应小于上一层。因此

R \leq Rstack [- 1], h \leq hstack [- 1]

接下来考虑体积效应。在第i层上方的蛋糕，其最小体积应对应R和h从1到i的情况，即

minV (i) = \sum_{n = 1}^{i} n^{2} * n = \frac{i (i + 1) (2 i + 1)}{6}

最大体积对应R和h逐层减1的情况，即

\begin{aligned} maxV (R, h, i) & = \sum_{n = 1}^{i} (R - n)^{2} (h - n) \\ = \sum_{n - 1}^{i} (R^{2} h - (R^{2} + 2 Rh) n + (h + 2 R) n^{2} - n^{3}) \\ = R^{2} h i - (R^{2} + 2 Rh) \frac{i (i + 1)}{2} + (h + 2 R) \frac{i (i + 1) (2 i + 1)}{6} - [\frac{i (i + 1)}{2}]^{2} \end{aligned}

合法的R和h应满足条件

N - n - maxV (R, h, i) \leq R^{2} h \leq N - n - minV (i)

我们将上一条件包装为check(R,h,i,n)，每次dfs之前都要检查。这是R和h满足的整体约束。

接下来考虑R和h的单独约束条件。前面我们得到

i + 1 \leq R \leq Rstack [- 1] - 1, i + 1 \leq h \leq hstack [- 1] - 1

除此之外，注意到下面两式：

h \geq i + 1, R^{2} h \leq N - n - minV (i)

联立得

R \leq \sqrt{\frac{N - n - minV (i)}{i + 1}}

因此R的实际约束范围是

i + 1 \leq R \leq \min (\sqrt{\frac{N - n - minV (i)}{i + 1}}, Rstack [- 1] - 1)

对R最大值的约束中，前者在蛋糕底部较强，后者在蛋糕顶部较强。

对R遍历上面的值，再次利用

R^{2} h \leq N - n - minV (i)

得到

h \leq \frac{N - n - minV (i)}{R^{2}}

因此h的实际约束范围是

i + 1 \leq h \leq \min (\frac{N - n - minV (i)}{R^{2}}, hstack [- 1] - 1)

同样地，对h最大值的约束中，前者在蛋糕底部较强，后者在蛋糕顶部较强。

特别地，对于最底层蛋糕，由于Rstack和hstack为空，只有前者约束有效。

最后考虑面积约束。如果当前已使用面积s大于之前算过的最优值S，就直接返回。

python

import math
N=int(input())
M=int(input())
# 对M==1特判
if M==1:
    S=float('inf')
    R=1
    while R**2<=N:
        if N%(R**2)==0:
            S=min(S,R**2+2*R*(N//(R**2)))
        R+=1
    print(S)
    exit()
S=float('inf')
flag=False
Rstack=[]
hstack=[]
def minV(i):
    return (i*(i+1)//2)**2
def maxV(R,h,i):
    return R**2*h*i-(R**2+2*R*h)*i*(i+1)//2+(2*R+h)*i*(i+1)*(2*i+1)//6-(i*(i+1)//2)**2
def check(R,h,i,n):
    return N-n-maxV(R,h,i)<=R**2*h<=N-n-minV(i)
def dfs(i,n,s):
    global S
    if s>=S:
        return
    # 底层蛋糕
    if i==M-1:
        if N<minV(i): # 无解
            return
        Rmin=i+1
        Rmax=int(math.sqrt((N-minV(i))/(i+1)))
        for R in range(Rmax,Rmin-1,-1):
            hmin=i+1
            hmax=int((N-minV(i))/R**2)
            for h in range(hmax,hmin-1,-1):
                if check(R,h,i,n):
                    Rstack.append(R)
                    hstack.append(h)
                    dfs(i-1,R**2*h,R**2+2*R*h)
                    Rstack.pop()
                    hstack.pop()
        return
    # 最顶层蛋糕要特判，刚好用完剩余体积
    if i==0:
        Rmin=math.ceil(math.sqrt((N-n)/(hstack[-1]-1)))
        Rmax=Rstack[-1]-1
        for R in range(Rmax,Rmin-1,-1):
            if (N-n)%(R**2)==0:
                h=(N-n)//(R**2)
                global flag
                flag=True
                S=min(S,s+2*R*h)
        return
    Rmin=i+1
    Rmax=min(Rstack[-1]-1,int(math.sqrt((N-n-minV(i))/(i+1))))
    for R in range(Rmax,Rmin-1,-1):
	    hmin=i+1
        hmax=min(hstack[-1]-1,int((N-n-minV(i))/(R**2)))
        for h in range(hmax,hmin-1,-1):
            if check(R,h,i,n):
                Rstack.append(R)
                hstack.append(h)
                dfs(i-1,n+R**2*h,s+2*R*h)
                Rstack.pop()
                hstack.pop()
dfs(M-1,0,0)
print(S) if flag else print(0)

T01190: 生日蛋糕 ​

T01190: 生日蛋糕