ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e899: 畢業(yè)舞會(huì)　解題心得

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

當(dāng)男生進(jìn)入會(huì)場(chǎng)，如果沒(méi)有女伴則會(huì)留在會(huì)場(chǎng)；當(dāng)女生進(jìn)入會(huì)場(chǎng)，如果沒(méi)有男伴與其配對(duì)，則會(huì)直接離開(kāi)會(huì)場(chǎng)。試問(wèn)，有多少種隊(duì)伍排列的方式，使得會(huì)場(chǎng)裡會(huì)配對(duì)出 N 個(gè)配對(duì)（即所有人皆有伴）。

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

因此，本題是很經(jīng)典的排列組合之問(wèn)題——卡塔蘭數(shù)（Catalan Number）。而其解可用動(dòng)態(tài)規(guī)劃解出，見(jiàn)維基之說(shuō)明、證明。

此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。

創(chuàng)作回應(yīng)

相關(guān)創(chuàng)作

更多創(chuàng)作