洛谷 P1754 球迷購票問題

P1754 球迷購票問題

盛況空前的足球賽即将舉行。球賽門票售票處排起了球迷購票長龍。

按售票處規定，每位購票者限購一張門票，且每張票售價為50元。在排成長龍的球迷中有N個人手持面值50元的錢币，另有N個人手持面值100元的錢币。假設售票處在開始售票時沒有零錢。試問這2N個球迷有多少種排隊方式可使售票處不緻出現找不出錢的尴尬局面。

例如當n=2是，用A表示手持50元面值的球迷，用B表示手持100元錢的球迷。則最多可以得到以下兩組不同的排隊方式，使售票員不至于找不出錢。

第一種:A A B B

第二種:A B A B

[程式設計任務]

對于給定的n (0≤n≤20),計算2N個球迷有多少種排隊方式，可以使售票處不至于找不出錢。

輸入格式：

一個整數，代表N的值

輸出格式：

一個整數，表示方案數

輸入樣例#1： 複制

輸出樣例#1： 複制

必開QWORD

測試：N=15

回溯:1秒（逾時）

模拟棧：大于10分鐘

遞歸算法：1秒（逾時）

動态規劃：0 MS

組合算法：16 MS

思路：

一：卡特蘭數

二：動态規劃。f[i][j]表示已經收了i個人的錢，現在手裡有j張50的。

那 當現在收的人的錢是50元時 f[i][j]+=f[i-1][j-1]。因為多一張50的，是以現在50元比起原來就多了一張。

     當現在收的人的錢是100元時  f[i][j]+=f[i-1][j+1]。因為要找一張50的，是以比起原來就少了一張50的。

細雨斜風作曉寒。淡煙疏柳媚晴灘。入淮清洛漸漫漫。

雪沫乳花浮午盞，蓼茸蒿筍試春盤。人間有味是清歡。