#18945: DP解思路跟另外一個可行的算法


qw227846@gmail.com (LJR~yam)

School : 嘉義市私立嘉華高級中學
ID : 71231
IP address : [61.60.245.65]
Last Login :
2019-11-24 10:57:30
e217. 同分異構物(國二理化) -- π | From: [61.60.245.65] | Post Date : 2019-08-15 22:03

DP解思路:

直接求烷烃數目的複雜度有點高,所以可以先求的n碳的烷基數目。

求得烷基個數後,回來討論烷烃的情況,會有以下幾種:

(1)碳數為偶數:

    1.可以分為兩個n/2個碳的烷基。

    2.不能分為兩個n/2個碳的烷基。(提示:要找到一個3度碳或4度碳當作中心,讓連結的烷基碳數都小於n/2,在做計算)

(2)碳數為奇數:

    1.可以分為一個(n+1)/2個碳的烷基,以及另一個(n-1)/2個碳的烷基。

    2.不能分為一個(n+1)/2個碳的烷基,以及另一個(n-1)/2個碳的烷基。(提示同上)

 

另一可行解法:

這題其實可以用 波利亞計數原理(polya enumeration theorem) 來解,有興趣的人,就去Google或圖書館找找吧。(ps.因為我也還沒懂)

 
ZeroJudge Forum