hdu 1502 Regular Words(java大数加法+dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1502

题意：ABC每个字母有n个，求满足要求的排列的个数：在该排列的任意前缀中满足 A的个数不少于B的个数 不少于C的个数。

思路：dp[i][j][k]表示该串由i个A，j个B，k个C组成，状态转移方程：dp[i][j][k] = dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]，并且i>=j>=k，（也就是串尾分别接A B C）

因为数据较大，需要高精度。为此，还专门学习了java基础入门。只是入门。。。

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

public class Main{
	public static void main(String[] args){
		BigInteger [][][]dp = new BigInteger [65][65][65];
		dp[0][0][0] = BigInteger.ONE;
		for(int i = 1; i <= 60; i++){
			for(int j = 0; j <= i; j++){
				for(int k = 0; k <= j; k++){
					dp[i][j][k] = BigInteger.valueOf(0);
					if(i>j) dp[i][j][k]=dp[i][j][k].add(dp[i-1][j][k]);
					if(j>k) dp[i][j][k]=dp[i][j][k].add(dp[i][j-1][k]);
					if(k>0) dp[i][j][k]=dp[i][j][k].add(dp[i][j][k-1]);
				}
			}
		}
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int x = cin.nextInt();
			System.out.println(dp[x][x][x]);
			System.out.println();
		}
}
}

hdu 1502 Regular Words(java大数加法+dp),布布扣,bubuko.com

hdu 1502 Regular Words(java大数加法+dp)

原文：http://blog.csdn.net/u013081425/article/details/20664557