网站建设维护内容,临沂网站制作企业,wordpress缓存数据库,网站 稳定性P1754 球迷购票问题 题目背景 盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。 按售票处规定#xff0c;每位购票者限购一张门票#xff0c;且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币#xff0c;另有N个人手持面值100元的钱币。假设… P1754 球迷购票问题 题目背景 盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。 按售票处规定每位购票者限购一张门票且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。 题目描述 例如当n2是用A表示手持50元面值的球迷用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式使售票员不至于找不出钱。 第一种:A A B B 第二种:A B A B [编程任务] 对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式可以使售票处不至于找不出钱。 输入输出格式 输入格式 一个整数代表N的值 输出格式 一个整数表示方案数 输入输出样例 输入样例#1 复制 2输出样例#1 复制 2说明 必开QWORD 测试N15 回溯:1秒超时 模拟栈大于10分钟 递归算法1秒超时 动态规划0 MS 组合算法16 MS 思路 一卡特兰数 #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n;
long long f[10000];
int main(){scanf(%d,n);f[0]f[1]1;for(int i2;in;i)for(int j0;ji;j)f[i]f[j]*f[i-j-1];coutf[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][j1]。因为要找一张50的所以比起原来就少了一张50的。 #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n;
int f[42][42];
int main(){scanf(%d,n);f[0][0]1;for(int i1;i2*n;i)for(int j0;jmin(i,n);j){if(j-10) f[i][j]f[i-1][j-1];if(ji) f[i][j]f[i-1][j1];}coutf[2*n][0];
} 转载于:https://www.cnblogs.com/cangT-Tlan/p/8045000.html
