主題

ZeroJudge - d054: 11310 - DELIVERY DEBACLE 解題心得

Not In My Back Yard | 2021-01-17 00:00:03 | 巴幣 0 | 人氣 59

題目連結:


題目大意:
現在有兩種蛋糕形狀如下圖所示:
一個為長寬皆為 1 單位長、一個為 L 形。

現在有寬度固定為 2 單位長但是有各式各樣長度的盒子,給定長度 n 試問有多少種裝蛋糕的方式。如下圖為裝 n = 2 之盒子的方法數:

輸入第一列給定一正整數 t ,代表有 t 筆測試資料,每筆佔一列。每列給定一正整數 n (1 ≦ n ≦ 40),代表盒子的長度,試問有多少種蛋糕的裝法?



範例輸入:
2
1
2


範例輸出:
1
5


解題思維:
跟這種問題很像,都是每一個 n 值之方法數與較小的 n 值之方法數有關。

如下圖,可以看到遞迴式為
其中 C(n) 代表長度 n 時裝蛋糕的方法數。

而已知 n = 0 、 1 、 2 時之方法數依序為 1 、 1 、 5 ,以此便可以推得 n = 3 、 4 、 ……以此類推。




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

創作回應

更多創作