P1754 球迷购票问题

    • 1.1K通过
    • 2.4K提交
  • 题目提供者 keyingkai
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 数论,数学 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

    按售票处规定,每位购票者限购一张门票,且每张票售价为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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。