[UVa] 10157 - Expressions

題目網址: http://goo.gl/okFQuw

題意:
(from luckycat)


解法: DP，對於某任何一種括號情況，我們都可以將最左邊的 "(" 以及與它配對的右括號拉出來看，可以寫成 "(A)B" ，若括號串長度為 n ，且題目給的 n 必是偶數(合法括號情況)，所求深度為 d ，則我們可以定義遞迴方程，為求方便我們令 m = n/2，假設 dp[m][d] 代表總共有 m 對括號且深度不大於 d 的狀況總數，將當前括號情況看成 "(A)B" 的話，則發現 A 的深度不能大於 d-1，B 的深度不能大於 d ，再枚舉 A 的長度來求出當前的所有情況數，而最後我們要求的是深度剛好等於 d ，所以最後要的答案是 dp[n/2][d] - dp[n/2][d-1]。

遞迴方程
dp[m][d] =
{ 1, if m = 0 & d >= 0
{ 0, if m > 0 & d = 0
{ sum( dp[k][d-1]*dp[m-k-1][d], 0 <= k < m ), if m > 0 & d > 0

TAG: DP, BigNum

注意: 需要用大數

程式碼:

	/**
	* Tittle: 10157 - Expressions
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/14
	*/
	// imports
	import java.util.*;
	import java.math.*;
	// problem class
	public class Main {
	private final static int N = 160;
	private static BigInteger dp[][] = new BigInteger[N][N];
	public static void main( String[] args ) {
	// declarations
	Scanner input = new Scanner(System.in);
	int n, d;
	// input
	while( input.hasNext() ) {
	n = input.nextInt();
	d = input.nextInt();
	// solve & output
	System.out.println( (solve(n/2,d).subtract(solve(n/2,d-1))).toString() );
	}
	input.close();
	}
	private static BigInteger solve( int n, int d ) {
	if( dp[n][d] != null ) return dp[n][d];
	if( n == 0 ) return dp[n][d] = BigInteger.ONE;
	if( n>0 && d==0 ) return dp[n][d] = BigInteger.ZERO;
	dp[n][d] = BigInteger.ZERO;
	for( int i=0; i <= n-1; ++i )
	dp[n][d] = dp[n][d].add( solve(i,d-1).multiply(solve(n-i-1,d)) );
	return dp[n][d];
	}
	}

view raw Main.java hosted with ❤ by GitHub