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：?復制 2 輸出樣例#1：?復制 2

說明

必開QWORD

測試：N=15

回溯:1秒（超時）

模擬棧：大于10分鐘

遞歸算法：1秒（超時）

動態規劃：0 MS

組合算法：16 MS

思路：

一：卡特蘭數

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; long long f[10000]; int main(){scanf("%d",&n);f[0]=f[1]=1;for(int i=2;i<=n;i++)for(int j=0;j<i;j++)f[i]+=f[j]*f[i-j-1];cout<<f[n]; }

二：動態規劃。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的。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int f[42][42]; int main(){scanf("%d",&n);f[0][0]=1;for(int i=1;i<=2*n;i++)for(int j=0;j<=min(i,n);j++){if(j-1>=0) f[i][j]+=f[i-1][j-1];if(j<=i) f[i][j]+=f[i-1][j+1];}cout<<f[2*n][0]; }

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/8045000.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的洛谷 P1754 球迷购票问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。