hdu1130&hdu1023

题目链接

hdu1130

hdu1023

题目概述

????????hdu1130让求的是\(n\)个结点构成的BST的数目.\((1\leq N \leq 100).\)

????????hdu1023让求的是\(n\)个火车进站出站形成的顺序的数目.\((1\leq N \leq 100).\)

解题思路

????????hdu1130求\(n\)个结点构成的BST的数目,就是求\(n\)个结点构成的不同形态的二叉树的数目,也就是\(C_n\).

????????hdu1023求\(n\)个火车进站出站形成的顺序的数目,实际也就是\(n\)个元素出栈入栈形成的序列的数目,解决的方法是把入栈看做\(+1\),出栈看做\(-1\),总共\(n\)次入栈操作,\(n\)次出栈操作,要求对于任意一个前项部分和\(\sum_{i=1}^k{a_i} \ge 0,\, (1 \leq k \leq 2n)\).对应的结果就是第\(n\)个\(Catalan\)数\(C_n\).

????????因为要求到第100项,所以要用要用大整数来做,所以选择java来做会方便很多.

代码实现

import java.math.BigInteger;
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        BigInteger[] ans = new BigInteger[105];
        ans[0] = new BigInteger("1");
        for (int i = 1; i <= 100; i++) {
            ans[i] = (ans[i - 1].multiply(new BigInteger(""+(4 * i - 2)))).divide(new BigInteger(""+(i+1)));
        }
        int n = 0;
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            n = in.nextInt();
            System.out.println(ans[n]);
        }
    }
}

是的,这两个题目提交的代码是同一个O(∩_∩)O哈哈~.

补充

hdu1130&hdu1023

原文：https://www.cnblogs.com/2018slgys/p/13293150.html