切換
舊版
前往
大廳
主題

ZeroJudge - e899: 畢業舞會　解題心得

Not In My Back Yard | 2020-03-04 00:07:06 | 巴幣 2 | 人氣 329
題目連結：
題目大意：
輸入有多列，每列給定一正整數 N （N ≦ 10000），代表有 N 位男生以及 N 位女生排成一列要依序進入會場。

當男生進入會場，如果沒有女伴則會留在會場；當女生進入會場，如果沒有男伴與其配對，則會直接離開會場。試問，有多少種隊伍排列的方式，使得會場裡會配對出 N 個配對（即所有人皆有伴）。

範例輸入：
1
2
10
範例輸出：
1
2
6789
解題思維：
可以視作是括號匹配的方法數。例如（（））、（）（）是合法的括號匹配但）（（）、）（）（等等不是。將「（」當作男生、「）」當作女生，即是本題的樣子。

因此，本題是很經典的排列組合之問題——卡塔蘭數（Catalan Number）。而其解可用動態規劃解出，見維基之說明、證明。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#動態規劃（Dynamic Programming）#數學#排列組合
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

團戰

看更多

相關創作

達人 春節加碼？ 從期望值來看賓果賓果能玩嗎？
15 1076
【數學】排列組合之組合表達式
0 76
鳥鳥玩數學-比較複雜的階梯問題(三種解法)(101中科實中教甄)
0 242
鳥鳥玩數學-試著用列舉的方法解錢包裡的錢可以換多少種款項(國小也能學得解法)
0 157
【zerojudge】c031. 00264 - Count on Cantor
0 36
達人 數學心得：314 國際數學日 圓周率日
7 754
【zerojudge】c002. 10696 - f91
0 48
【zerojudge】b901+d715 階乘最後一位非零數
0 84
分享一道男生特別有感的排列組合難題
0 132
達人 霧島簡評113學測數學A
16 1370
08. 給初學者練習PGA2D運用邏輯的網頁小遊戲
0 50
【zerojudge】b810 - 九○七四二的問題之(二)
0 76
達人 這題有錯！112 數學A 模擬考—「已知一點與兩角平分線，求原三角形」
6 651
達人 介紹數學遊戲 Renzoku 連續 - 離散世界的「連續」
16 627
【隨筆】六邊形球體
3 189
數學少女的啟發
0 112
07. PGA2D，點與線的表示法
0 60
惡作劇隨筆系列2
0 57
達人 錯誤的學習數學心態與方法
33 1558
達人 書評：數學女孩秘密筆記：圖形的證明 – 為何要證明？
14 1049

更多創作

追蹤 創作集
其他創作
作品資料夾