UVA_10157

     我们可以把最左边的“(”和其配对的“)”看成一组分界线，它们把剩余的括号分成了内外两部分，其中里面的部分深度最多为d-1，外面部分的深度最多为d。我们不妨设f[i][j]表示一共有i对括号时深度不超过j的表达式的数量，那么f[i][j]=sum{f[k][j-1]*f[i-k-1][j]}，最后输出的结果即是f[n/2][d]-f[n/2][d-1]，当然前提是n为偶数。

import java.math.BigInteger; import java.util.Scanner; public class Main {
   public static void main(String[] args)     {
           Scanner cin = new Scanner(System.in);         BigInteger[][] f = new BigInteger[160][160]; for(int i = 0; i <= 150; i ++)             f[0][i] = new BigInteger("1"); for(int i = 1; i <= 150; i ++) for(int j = 0; j <= 150; j ++)                 f[i][j] = new BigInteger("0"); for(int i = 1; i <= 150; i ++) for(int j = 1; j <= 150; j ++) for(int k = 0; k < i; k ++)                     f[i][j] = f[i][j].add(f[k][j - 1].multiply(f[i - k - 1][j])); while(cin.hasNext())         {
   int n = cin.nextInt(); int d = cin.nextInt(); if(n % 2 == 1)                 System.out.println("0"); else             {
                   n /= 2;                 System.out.println(f[n][d].add(f[n][d - 1].negate()));             }         }     } }