首页 > 代码库 > UVa 10157 - Expressions

UVa 10157 - Expressions

题目:给你n个括号,求合法的匹配中,深度不超过d的组合数。

分析:组合,计数,dp,大整数。

          这个题目很像卡塔兰数,不过深度有限制,可以利用卡塔兰数的递推公式求解;

          设C(k,d)为k对括号形成深度不超过d的合法匹配方法数;则有:

           C(k,d)= Σ(C(i,d-1)*C(k-1-i,d)) { i 取0到 k-1 }

          (按卡塔兰数递推,k对括号分成两组,左边i个生成串A,右边k-1-i个生成串B,

             还有一对在A外,形成(A)B形式;这时A的深度最大为d-1,B的深度最大为d)

          因此,深度为d的方案数为:C(k,d)- C(k,d-1)。

说明:觉得会TLE,竟然AC了(⊙_⊙)。

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int C[151][151][51] = {0};
int ans[51];
 
int main()
{
	for (int i = 0 ; i < 151 ; ++ i)
		C[0][i][0] = 1;
		
	for (int j = 1 ; j < 151 ; ++ j)
	for (int i = 1 ; i < 151 ; ++ i)
	for (int k = 0 ; k < i ; ++ k) {
		for (int p = 0 ; p < 25 ; ++ p)
		for (int q = 0 ; q < 25 ; ++ q)
			C[i][j][p+q] += C[k][j-1][p]*C[i-1-k][j][q];
		for (int p = 0 ; p < 50 ; ++ p) {
			C[i][j][p+1] += C[i][j][p]/10000;
			C[i][j][p] %= 10000;
		}
	}

	int n,m;
	while (~scanf("%d%d",&n,&m)) {
		for (int i = 0 ; i < 50 ; ++ i)
			ans[i] = C[n/2][m][i] - C[n/2][m-1][i];
		for (int i = 0 ; i < 50 ; ++ i)
			while (ans[i] < 0) {
				ans[i] += 10000;
				ans[i+1] -= 1;
			}
			
		int e = 49;
		while (e > 0 && !ans[e]) -- e;
		printf("%d",ans[e --]);
		while (e >= 0) printf("%04d",ans[e --]);
		printf("\n");
	}
	return 0;
}

UVa 10157 - Expressions