主題

ZeroJudge - d389: 11069 - A Graph Problem 解題心得

Not In My Back Yard | 2021-02-14 00:00:01 | 巴幣 0 | 人氣 21

題目連結:


題目大意:
輸入有多筆測試資料,每筆佔一列。每列給定一正整數 n (1 ≦ n ≦ 76),代表有一種特殊的無向圖其有 n 個節點(如下圖所示)。

試問有多少方法可以從中取出一部份的節點成為一子集合使得:
沒有任何節點是相鄰的(相鄰節點為如上圖的節點 1 與節點 2 這種有邊相接之節點);
加入其他未取的節點到此子集合中必會與其中某些節點相鄰。

例如 n = 5,合法的子集合為以下四種:
{ 1, 3, 5 } 、 { 1, 4 } 、 { 2, 4 } 、 { 2, 5 }



範例輸入:
1
2
3
4
5
30


範例輸出:
1
2
2
3
4
4410


解題思維:
考慮一個足夠大的 n 值(此例為 n ≧ 4),並假設 D[i] 為 i 個節點能取的所求子集合之方法數。

可以看到當我們取第 n 個節點時,第 n - 1 個節點不可能會被取;相反地,當取第 n - 1 個節點時,就取不了第 n 個節點。而且因為所求之子集合定義的緣故,我們必須取節點 n 與節點 n - 1 兩者其中之一。

因此,D[n] = (有取節點 n 的方法數) + (有取節點 n - 1 的方法數)。



而有取節點 n 的方法數恰為 D[n - 2]。為何?因為正如 n 個節點,有 n - 2 個節點時,你必須取節點 n - 2 或是節點 n - 3 。

不管如何,一定符合子集合的第一條性質——取的節點之間必不相鄰。

那麼第二條性質呢?假設你取的是節點 n - 2 (< n - 2 的節點隱含於 D[n - 2] 裡所以不需討論),而你唯一介於 n ~ n - 2 之間的節點只有節點 n - 1,而取它將會與節點 n 和節點 n - 2 相鄰;如果取的是節點 n - 3,則剩下 n - 1 與 n - 2,前者與節點 n 相鄰、後者與節點 n - 3 相鄰。所以實際上第二條性質也符合。

類似地,有取節點 n - 1 的方法數恰好為 D[n - 3] (將上面的論述的節點編號全部 - 1 即可得到)。



所以我們得到了一個遞迴式:
D[n] = D[n - 2] + D[n - 3]
而我們可以先建表(先求出較小 n 值,然後一路推到大的 n 值。已知 D[1] = 1 、 D[2] = 2 、 D[3] = 2)。然後對輸入的 n 值,輸出對應之 D[n]。




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

創作回應

更多創作