HDU 1134( Game of Connections Catalan数的第三种应用!)

spoiler posted @ 2011年4月24日 04:59 in Catalan数的各种应用 , 1488 阅读

给定N*2个点,求分别将其两两相连,每个点仅链接一次,而且每条线段不相交!

题目分析:

这又是Catalan数

直接套公式吧,其实证明目前我还没会,嘎嘎

公式:

f[n]=$$\sum_{k=0}^{n-1}{{f[n-1-k]*f[k]}}$$;

直接计算就可以了,这里设计到大数的运算,我是用JAVA写的,不想用C模拟了 呵呵

代码:

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String args[]){
		List list=new ArrayList(102);
		BigInteger f=BigInteger.valueOf(1);
		list.add(f);
		list.add(f);
		f=BigInteger.valueOf(2);
		list.add(f);
		for(int i=3;i<=100;i++){
			BigInteger sum=BigInteger.valueOf(0);
			for(int j=0;j<i;j++){
				sum=sum.add( ((BigInteger)list.get(i-1-j)).multiply( ((BigInteger) list.get(j) )) );
			}
			list.add(sum);
		}
		Scanner cin=new Scanner(System.in);
		int n;
		while(cin.hasNext()){
			n=cin.nextInt();
			if(n==-1)
				break;
			System.out.println(list.get(n));
		}
	}
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter