hdu1130&hdu1023

题目链接

hdu1130

hdu1023

题目概述

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

        hdu1023让求的是(n)个火车进站出站形成的顺序的数目.((1leq 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哈哈~.

补充