原题

毒瘤DP......从lyd的蓝书上看到的题目，然后我昨晚就调了一晚上，今早一来发现是DP状态搞反了......

题意：

一个只由“( )”,“[ ]”,“{ }”构成的字符串，若“( )”内没有“[ ]”,“[ ]”内没有“{ }”,则称这样的字符串为SS表达式（空串也是SS表达式）。现在需要求出有L1个大括号，L2个中括号，L3个小括号，深度为D的SS表达式的数量。

解析：

考虑DP。如果我们用表示i个小括号，j个中括号，k个小括号，深度为d时的方案总数，我们会发现这个方程很难转移，因为不知道深度为d-1的表达式表达式的具体形态，没法从d-1推出d。所以我们改变一下状态表示，表示深度小于等于d时的方案总数。即使这样，我们发现这个转移依然非常棘手。我们不妨换个思路，如果已经得到一个深度为d-1的表达式A，那么我们可以生成哪些深度为d的SS表达式呢？显然，可以有(A)B,[A]B,{A}B这三种情况。我们来依次讨论。

1.  (A)B，这时A中只含有(),所以j=0,k=0，所以我们可以枚举A中()的数量；
2. [A]B，这时 A中不含有[],即k=0,枚举A中()与[]的数量
3. {A}B，这时A中可以有三种括号，依次枚举

这样我们就能写出整个DP的转移方程（方程太复杂了，我就借dalao的图用一下了）：

 

       这题的代码还有很多细节，像,i=0,j=0,k=0时需全部赋成1（否则后面转移时会把所有项变成0），这样操作导致后面输出答案时我们要对i=0;j=0;k=0的情况进行特判。

同时，因为答案是，所以我们还需要特判d=0的情况。

 完整代码如下：

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ull  int
il int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
    while(ch<='9'&&ch>='0') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
#define Mod 11380
int L1,L2,L3,D; //L1小括号，L2中括号，L3大括号，D深度 
ull f[20][20][20][37];
ull sum1(int i,int j,int k,int d) {
    ull sum=0;
    for(int p1=0;p1<i;p1++) {
        sum+=f[i-p1-1][j][k][d]*f[p1][0][0][d-1];
        sum%=Mod;
    }
    return sum;
}
ull sum2(int i,int j,int k,int d) {
    ull sum=0;
    for(int p1=0;p1<=i;p1++) {
        for(int p2=0;p2<j;p2++) {
            sum+=f[i-p1][j-p2-1][k][d]*f[p1][p2][0][d-1];
            sum%=Mod;
        }
    }
    return sum;
}
ull sum3(int i,int j,int k,int d) {
    ull sum=0;
    for(int p1=0;p1<=i;p1++) {
        for(int p2=0;p2<=j;p2++) {
            for(int p3=0;p3<k;p3++) {
                sum+=f[i-p1][j-p2][k-p3-1][d]*f[p1][p2][p3][d-1];
                sum%=Mod;
            }
        }
    }
    return sum;
}
void deal() {
    for(int i=0;i<=L3;i++) {
        for(int j=0;j<=L2;j++) {
            for(int k=0;k<=L1;k++) {
                if(i==0 && j==0 && k==0) continue;
                for(int d=1;d<=D;d++) {
                    f[i][j][k][d]+=sum1(i,j,k,d)+sum2(i,j,k,d);
                    f[i][j][k][d]%=Mod;
                    f[i][j][k][d]+=sum3(i,j,k,d);
                    f[i][j][k][d]%=Mod;
                }
            }
        }
    }
}
int main() {
    L1=read(); L2=read(); L3=read(); D=read();
    memset(f,0,sizeof(f));
    for(int i=0;i<=D;i++) f[0][0][0][i]=1;
    deal();
    if(D==0) {
        if(L1==0 && L2==0 && L3==0)
            printf("1\n");
        else 
            printf("0\n");
        return 0;
    }
    if(L1==0 && L2==0 && L3==0) printf("0\n");
    else printf("%d\n",(Mod+f[L3][L2][L1][D]-f[L3][L2][L1][D-1])%Mod);
    return 0;
}

完。