#include <stdio.h>
#define MOD(x) (((x) + 11380) % 11380)
int L1, L2, L3, D, f[11][11][11][31];
inline int part(int ma, int mb, int mc, int md,
int a, int b, int c
)
{
return MOD(f[a][b][c][md - 1] * f[ma - a][mb - b][mc - c][md]);
}
inline int calc(int ma, int mb, int mc, int md)
{
int a, b, c, r;
if (!ma && !mb && !mc)
return 1;
r = 0;
if (mc) {
for (c = 0; c <= mc - 1; c++)
r = MOD(r + part(ma, mb, mc - 1, md, 0, 0, c));
}
if (mb) {
for (b = 0; b <= mb - 1; b++)
for (c = 0; c <= mc; c++)
r = MOD(r + part(ma, mb - 1, mc, md, 0, b, c));
}
if (ma) {
for (a = 0; a <= ma - 1; a++)
for (b = 0; b <= mb; b++)
for (c = 0; c <= mc; c++)
r = MOD(r + part(ma - 1, mb, mc, md, a, b, c));
}
return r;
}
int main()
{
int a, b, c, d;
freopen("e:\\in.txt", "r", stdin);
scanf("%d%d%d%d", &L1, &L2, &L3, &D);
f[0][0][0][0] = 1;
for (d = 1; d <= D; d++)
for (a = 0; a <= L1; a++)
for (b = 0; b <= L2; b++)
for (c = 0; c <= L3; c++)
f[a][b][c][d] = calc(a, b, c, d);
printf("%d\n", D ? MOD(f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]) :
MOD(f[L1][L2][L3][D])
);
return 0;
}
思路：
把括号的嵌套看成是一棵树就简单点了。
这棵树的最大深度为 D。()节点下面不能有{}[]节点，[]节点下面不能有{}节点。
然后我们从上往下依次摆放节点。
考虑只有()节点的情况。
如果 f[n][d] 表示现在有n个节点需要摆放，深度小于等于d。
那么当前节点的下面可以摆 1，2 ... n 个节点。
摆完当前节点之后，剩下的在右边继续摆。
总方案数就是等于 下面的方案数*右边的方案数
考虑三种节点都有的情况，实际上只是比上面的问题复杂一点点而已。
如果 f[a][b][c][d] 表示现在有a个{}节点，b个[]节点，c个()节点需要摆放。
当前节点摆 () 的时候，下面就只能摆 ()，其余的全放在右边。
当前节点摆 [] 的时候，下面就只能摆 ()[]，。。。
。。。
这题的复杂度是 O(L1*L1*L2*L2*L3*L3*D)。
看上去比较大，但是可以AC的~
之前自己想的方法是 f[a][b][c][d] 表示深度等于d的方案数，而不是小于。
最后答案为 f[L1][L2][L3][D]。
复杂度多乘了一个D，就TLE了。
后来看了别人方法，发现保存深度小于等于d，这样的话会好一些。
最后答案为 f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]
这方法实在牛逼！
代码：