主題

ZeroJudge - a044: 空間切割 解題心得

Not In My Back Yard | 2021-01-11 00:00:14

題目連結:


題目大意:
輸入有多列,每列給定一正整數 n ,試問在三維座標空間裡放置 n 個平面最多可以將空間切為幾個區域?



範例輸入:
1
2


範例輸出:
2
4


解題思維:
參見這題,可以看到子區域個數會是
(n, 0) + (n, 1) + (n, 2) + (n, 3)
其中 (n, k) 為 n 個物品取 k 個之方法數。

上式可以展開為
1 + n + n(n - 1) ÷ 2 + n(n - 1)(n - 2) ÷ 6
通分並合併項次可得公式
(n ^ 3 + 5n + 6) ÷ 6

要讓運算數降低的話,可以改寫為
n(n ^ 2 + 5) ÷ 6 + 1




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
72 巴幣: 0

創作回應

相關創作

更多創作