传送门 题目废话太多。 就是n个球最多能把空间划分成多少个部分。 尝试下n = 3的情况想象下……再看下面的内容……
对n维区域用m个求划分，答案记为f(n, m)
对于第m个球，那么最优情况是它与所有球相交（显然成立） 然后相交时球是n维的，球面是n-1维的，球面与球面的交集是n - 2维的 （自己脑洞N=3的情况） 其它球面来划分这个球面，相当于把n - 1维区域用m - 1个n - 2维的平面来划分（很正确呀） 而n - 2维的这种平面必然是n - 2维的球，因为是球面与球面相交嘛（一维空间的球是平面，特此声明）
每个区域都对应着一个n维区域 最多可以把球面划分成f(n - 1, m - 1)个区域 那么这个球内就有f(n - 1, m - 1)个空间 还要加剩下的球~就是f(n, m - 1)
立即推出：f(n, m) = f(n - 1, m - 1) + f(n, m - 1) 边界条件咱就不说了……YY下就出来了
至于为啥这是最优的我也不知道
var
n,m,i,j:longint;
f:
array [
0..
25,
0..
105]
of int64;
begin
read(m,n);
f[
0,
0]:=
1;
for j:=
1 to m
do f[
0,j]:=
2;
for i:=
1 to n
do begin
f[i,
0]:=
1;
for j:=
1 to m
do f[i,j]:=f[i,j-
1]+f[i-
1,j-
1];
end;
write(f[n,m]);
end.
转载请注明原文地址: https://ju.6miu.com/read-147.html
