令$f(a,b,c,k)$为$a\times b\times c$的长方体的第k层覆盖所需要的单位立方体数,则有
$$f(a,b,c,1)=2ab+2bc+2ac.$$
该文中提供了$f(a,b,c,k)$的这样一种计算方式:把第k次覆盖所得的图形分别向前后左右上下移动一步,这六者的并集即第k+1次覆盖所得的图形,再由观察可得递推式
$$f(a,b,c,k)=f(a,b,c,k-1)+4(a+b+c)+8(k-2).$$
直接递推得
$$f(a,b,c,k)=2(ab+bc+ac)+4(k-1)(a+b+c)+4(k-1)(k-2)=(a+b+c+2(k-1))^2-a^2-b^2-c^2-4(k-1).$$
为$f(a,b,c,k)$选择一个合适的上界(以下使用的是20000),遍历$a,b,c,k$的所有可能组合(大约有三百万个)可得结果$18522$。
def f(a,b,c,d):
return (a+b+c+2*(d-1))**2-a*a-b*b-c*c-4*(d-1)
target=20000
s=[0]*target
x=1
while f(x,x,x,1) < target:
y=x
while f(x,y,y,1) < target:
z=y
while f(x,y,z,1) < target:
k=1
while f(x,y,z,k) < target:
s[f(x,y,z,k)]+=1
k+=1
z+=1
y+=1
x+=1
print min(z for z in range(target) if s[z]==1000)
|