原题链接
思路:
看的是lyd老师的题解
dp状态找的很巧妙：
d p [ i ] [ j ] [ k ] [ l ] dp[i][j][k][l]dp[i][j][k][l]表示深度不超过i ii，用了j jj对花括号，k kk对中括号，l ll对小括号组成的括号序列的数量。
这样只需要枚举四层：
枚举深度 枚举花括号的个数 枚举中括号的个数 枚举小括号的个数
枚举的顺序也是要注意的，因为S S SSSS表达式的要求。
接下来考虑转移：
划分依据是将括号序列分为第一部分和第二部分。
由于两个S S SSSS序列拼接时，深度为m a x ( d 1 , d 2 ) max(d1,d2)max(d1,d2)，所以第二部分的长度可以为[ 1 , i ] [1,i][1,i]中的任意数，对应到d ddp pp数组的第一维为i ii。
由于是求的数量，所以是乘法原理，根据第一部分最外层的不同括号进行再次枚举。
比如当第一部分最外层为花括号时，第一部分里面可以是花括号、中括号、小括号，就要进行三层for枚举。
for(int p=1;p<=j;p++) for(int q=0;q<=k;q++) for(int r=0;r<=l;r++) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][p-1][q][r]*dp[i][j-p][k-q][l-r])%mod;
假设第一部分花费了p pp个花括号，q qq个中括号，r rr个小括号，留给第二部分的就是j − p j-pj−p个花括号，k − q k-qk−q个中括号，l − r l-rl−r个小括号。由于第一部分的最外层已经确定是花括号了，所以对应转移的深度范围也变成了[ 1 , i − 1 ] [1,i-1][1,i−1]，对应dp的第一维为i − 1 i-1i−1。
代码：
///#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn = 2e5 + 7,mod=11380; int dp[31][11][11][11],l1,l2,l3,l4,d; int main() { l1=read,l2=read,l3=read,d=read; for(int i=0;i<=d;i++) dp[i][0][0][0]=1; for(int i=1;i<=d;i++)///枚举深度 for(int j=0;j<=l1;j++) for(int k=0;k<=l2;k++) for(int l=0;l<=l3;l++){ if(j>0){///第一层最外层是{} for(int p=1;p<=j;p++) for(int q=0;q<=k;q++) for(int r=0;r<=l;r++) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][p-1][q][r]*dp[i][j-p][k-q][l-r])%mod; } if(k>0){///第一层最外面是[] for(int q=1;q<=k;q++) for(int r=0;r<=l;r++) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][0][q-1][r]*dp[i][j][k-q][l-r])%mod; } if(l>0){ for(int r=1;r<=l;r++) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][0][0][r-1]*dp[i][j][k][l-r])%mod; } } int tmp=dp[d][l1][l2][l3]; if(d) tmp-=dp[d-1][l1][l2][l3]; if(tmp<0) tmp=(tmp+mod)%mod; cout<<tmp; return 0; }
