专栏首页ml卡特兰数扩展

卡特兰数扩展

对于排队买票问题的一些说法.....

  假若有M+ N人去买票,n人手持5元,m人手持10元,而售货阿姨没有零钱,问有多少种方法能使大家都买到票。

其中m<=n.M+N<=10;(初次在HBUOJ上看到.....)

    (1) 有已知条件 m<=n; 我们就不需要去考虑m>n时的情况啦!但是即便去考虑的话,这种情况依旧为零.

因为m>n时,你不管这么排列都是不可能找开的...m*10-n*5>m*5----所以这个条件只是为我们减少了一小部分的时间.

    (2) m<=n时,我们发现对于随意的第K个位置出现的10多余5的时候不可能的情况 我们都可以找到

 对应的可以满足的情况 。

  比如  10 5 10 10 5  5  我们只需将后面的10 和5 换一下就行, 5 10 5 5 10 10 。

再比如 10 5 10 5 5 我们只需将  5 10 5 5 10 (m<=n)

       那,我们总的分配情况为C(m+n,m) ,然后不能的情况为C(m+n,n+1)(m+1>n)

 最后加上分配排列就是(C(m+n,m)-C(m+n,n+1))*m!*n! 

化解之后为: (m+1-n)*(m+n)!/(m+1);

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ubuntu16中遇到libgstreamer-0.10.so.0缺失解决方案

    1.  error while loading shared libraries: libgstreamer-0.10.so.0: cannot open sh...

    Gxjun
  • HDUOJ----2571(命运)(简单动态规划)

    命运 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

    Gxjun
  • hdu------(1757)A Simple Math Problem(简单矩阵快速幂)

    A Simple Math Problem Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32...

    Gxjun
  • 不同时间复杂度的规模上限

    饶文津
  • Leetcode-Easy 806. Number of Lines To Write String

    给一个字符串S,从左到右将它们排列行,每行最大长度为100,,同时给定一个数组withds,widths[0]对应着 a的宽度, widths[1]对应着b的宽...

    致Great
  • 互联网行业法律动态报告(2014年10月)

    互联网行业法律动态报告(2014年10月) 腾讯互联网与社会研究院法律研究中心 重点摘要: 2014年10月,网络治理、知识产权、竞争规则、电子商...

    腾讯研究院
  • 互联网法律动态报告(10月版)

    互联网法律动态报告(10月版) 腾讯互联网与社会研究院 法律研究中心 重点摘要: ●2014年10月,网络治理、知识产权、竞争规则、电子商务、互联...

    腾讯研究院
  • R中的向量化运算

    1、R中的向量化运算-seq seq(1, 10, by=1) seq(1, 10, by=0.1) seq(1.9, 10, by=0.1) #注意,不...

    Erin
  • LeetCode 806. 写字符串需要的行数

    我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果我们在写某个字母的时候会使这行超过了100 个单位,那么我们应该把这个字母写...

    Michael阿明
  • leetcode-806-Number of Lines To Write String

    chenjx85

扫码关注云+社区

领取腾讯云代金券