首页 > 代码库 > HDU 1131

HDU 1131

2024-07-25 21:12:15   220人阅读

N个节点的不同的树的数目。这样

随便取一个节点作为根，那么他左边和右边的儿子节点个数就确定了，假定根节点标号为x，那么左子树的标号就从1到x-1,共x-1个，右子树的标号就从x+1到n，共n-x个，那么我们的x从1取到n，就获得了所有的情况数。

这是一个递推的式子，初始值与卡特兰数的初值相同。所以，解正是卡特兰数。又由于节点有序，所以乘上N!。

import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;import java.io.InputStreamReader;class Cont{	BigDecimal []num;	Cont(){		num=new BigDecimal[110];		num[0]=new BigDecimal(1);		BigDecimal Tmp;		for(int i=1;i<=100;i++){			Tmp=new BigDecimal(i);			num[i]=num[i-1].multiply(Tmp);		}	}}public class Main{    public static void main(String args[]){        Scanner in=new Scanner(System.in);        BigDecimal []Can=new BigDecimal[110];        Can[0]=new BigDecimal(1);        BigDecimal B,C,D;        Cont Conmul=new Cont();        for(int i=1;i<=100;i++){            B=new BigDecimal(4*i-2);            C=new BigDecimal(i+1);            D=Can[i-1].multiply(B);            Can[i]=D.divide(C);        }        while(in.hasNext()){    	int x=in.nextInt();	if(x==0) break;	BigDecimal ans=new BigDecimal(1);	ans=ans.multiply(Can[x]);	ans=ans.multiply(Conmul.num[x]);	System.out.println(ans);        }    }}

　　

HDU 1131


联系
我们