题目:http://poj.org/problem?id=3088
题意:
给出一个整数B (1<&#61;B<&#61;11), 表示有1 2 3 ... B 这B个数, 可选择其中的N (1<&#61;N<&#61;B)个数(不用按顺序), 并用若干个括号将它们括起来.
如B &#61; 2 时:
有 (1), (2), (12), (1)(2), (2)(1) 这5种情况
要求出所有情况的总数.
解题思路:
看懂题意后, 马上做的是找算公式找规律, 但式子很复杂. 半途而废了. 后来找出了一条DP式如下:
设D[i] 表示有 i 个数时可以组成的所有情况总数
那么有
D[i] &#61; C(i, 1) * D[1] &#43; C(i, 2) * D[2] &#43; .. C(i, i - 1) * D[i - 1] &#43; 1;
(从别算出从i 个数中选取 k个的取法总数, 即C(i, 1), 而前边已算出D[k]的个数, 那么从i个数中选取k个数之后用括号括题来的总数为C(i, k) * D[k]).
其实上面的递推式是错误的, 比赛时也因为推出D[2] &#61; 3, 与正确答案5不同, 所以放弃了这题. 想想可惜了.
上面的式子忽略了从i个数中选取i个数的情况, 也就是 &#43;1是错误的, 正确应该是&#43;2&#xff3e;i - 1&#xff0e;
#include
#include
__int64 C[MAX][MAX];
__int64 D[MAX];
__int64 Dec;
int main()
{int i, j;for(i &#61; 0; i