洛谷 P1754 球迷购票问题
2024-08-28 12:13:24
题目背景
盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。
按售票处规定,每位购票者限购一张门票,且每张票售价为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的值
输出格式:
一个整数,表示方案数
输入输出样例
说明
必开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[];
int main(){
scanf("%d",&n);
f[]=f[]=;
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
f[i]+=f[j]*f[i-j-];
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[][];
int main(){
scanf("%d",&n);
f[][]=;
for(int i=;i<=*n;i++)
for(int j=;j<=min(i,n);j++){
if(j->=) f[i][j]+=f[i-][j-];
if(j<=i) f[i][j]+=f[i-][j+];
}
cout<<f[*n][];
}
最新文章
- ORA-06502:PL/SQL :numberic or value error: character string buffer too small
- Thinkphp 用PHPExcel 导入Excel
- Back to Edit Distance(LCS + LIS)
- hadoop 分布式缓存
- JS获取屏幕,浏览器,网页高度宽度
- sed替换字符串时,使用正则表达式的注意事项
- I2总线
- QML设计登陆界面
- url&;视图
- webapi拦截请求
- HDU6235-Permutation-水题-2017中国大学生程序设计竞赛-哈尔滨站-重现赛
- php + 和 array_merge的区别
- centos 7查看防火墙报错(已解决,之前安装过python3)
- leetcode 刷题(3)--- 无重复字符的最长子串
- 搭建vsftpd服务
- Jupyter-NoteBook-你应该知道的N个小技巧
- 【模板】Tarjan scc缩点
- 恶意代码分析-使用apataDNS+inetsim模拟网络环境
- C++for的几种方式
- Zookeeper 系列(三)Zookeeper API