首页 > 代码库 > hdoj 1133 Buy the Ticket 【卡特兰】

hdoj 1133 Buy the Ticket 【卡特兰】

题意:有m个人(拿50元)和n个人(拿100元)去买票,售票厅刚开始没有,问最后所有人都能够买到的方式的种类数。

这道题也是经典的卡特兰数类型题。

我们可以将他们看做是火车进出站,但是由于人是不同的,所以最后还要乘上m!*n!

最后的数学表达是就是(C(m+n,n)-C(m+n, m+1))*m!*n!=》 结果为 (m!*n!)*(m+1-n)/(m+1)

注:m<n时 直接输出0

代码:

import java.util.Scanner;
import java.math.*;

public class Main{
    
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        BigInteger[] s = new BigInteger[220];
        s[1] = new BigInteger("1");
        int i;
        for(i = 2; i < 220; i ++){
            BigInteger c = new BigInteger(((Integer)i).toString());
            s[i] = new BigInteger("1");
            s[i] = s[i-1].multiply(c);
            //System.out.println(s[i]);
        }
        int n, m, v = 0;
        while(cin.hasNext()){
            m = cin.nextInt();
            n = cin.nextInt();
            if(n == 0&&m ==0) return;
            v++;
            System.out.println("Test #"+v+":");
            if(m < n){
                System.out.println("0"); continue;
            }
            BigInteger temp1 = new BigInteger(((Integer)(m+1-n)).toString());
            BigInteger temp2 = new BigInteger(((Integer)(m+1)).toString());
            BigInteger ans = s[n+m];
            ans = ans.multiply(temp1);
            ans = ans.divide(temp2);
            System.out.println(ans);
        }
    }
}
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1133

hdoj 1133 Buy the Ticket 【卡特兰】