首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。