#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。()節(jié)點下面不能有{}[]節(jié)點，[]節(jié)點下面不能有{}節(jié)點。
然后我們從上往下依次擺放節(jié)點。
考慮只有()節(jié)點的情況。
如果 f[n][d] 表示現(xiàn)在有n個節(jié)點需要擺放，深度小于等于d。
那么當前節(jié)點的下面可以擺 1，2 ... n 個節(jié)點。
擺完當前節(jié)點之后，剩下的在右邊繼續(xù)擺。
總方案數(shù)就是等于 下面的方案數(shù)*右邊的方案數(shù)
考慮三種節(jié)點都有的情況，實際上只是比上面的問題復(fù)雜一點點而已。
如果 f[a][b][c][d] 表示現(xiàn)在有a個{}節(jié)點，b個[]節(jié)點，c個()節(jié)點需要擺放。
當前節(jié)點擺 () 的時候，下面就只能擺 ()，其余的全放在右邊。
當前節(jié)點擺 [] 的時候，下面就只能擺 ()[]，。。。
。。。
這題的復(fù)雜度是 O(L1*L1*L2*L2*L3*L3*D)。
看上去比較大，但是可以AC的~
之前自己想的方法是 f[a][b][c][d] 表示深度等于d的方案數(shù)，而不是小于。
最后答案為 f[L1][L2][L3][D]。
復(fù)雜度多乘了一個D，就TLE了。
后來看了別人方法，發(fā)現(xiàn)保存深度小于等于d，這樣的話會好一些。
最后答案為 f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]
這方法實在牛逼！
代碼：