本题是一道线性 dp 的题目。
由于数据范围比较小,我们设状态是怎么暴力怎么来,转移也是怎么费劲怎么来。。直接设 $f_{i,j,k,l}$ 表示深度是 $i$,三个括号分别用 $j,k,l$ 个的方案数,转移方程也比较好想,就不赘述了。
但是,如果用 $i$ 一维来表示深度不超过 $i$,转移方程、代码实现都会更容易。
初始状态显然 $f_{i,0,0,0}=1$,因为此时 $i$ 表示“不超过这个深度”
转移方程嘛,偷张图过来。。。
https://cdn.luogu.com.cn/upload/image_hosting/t5hdd54n.png
我这里来解释一下:深度不超过 $D-1$,内部括号数分别为 $i,j,k$ 的方案与深度不超过 $D$,括号数分别为 $l_1-i-1,l_2-j,l_3-k$ 的状态合并所表示的含义确实是 $f_{D,l_1,l_2,l_3}$,且两个状态的方案相互独立,所以统计时应该相乘再求和。由于不能出现小括号包含中括号之类的限制,所以求小括号分割的方案数时,内部中括号大括号数都必须是零。
贴上代码:
#include <bits/stdc++.h>
using namespace std;
const int N=3e1+7;
const int mod=11380;
int f[N][N][N][N];
int d,l1,l2,l3;
int main(void)
{
scanf("%d%d%d%d",&l1,&l2,&l3,&d);
for(int i=0;i<=d;i++)
f[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)
for(int a=1;a<=j;a++)
for(int b=0;b<=k;b++)
for(int c=0;c<=l;c++) {
f[i][j][k][l]+=f[i-1][a-1][b][c]*f[i][j-a][k-b][l-c];
f[i][j][k][l]%=mod;
}
if(k)
for(int b=1;b<=k;b++)
for(int c=0;c<=l;c++) {
f[i][j][k][l]+=f[i-1][0][b-1][c]*f[i][j][k-b][l-c];
f[i][j][k][l]%=mod;
}
if(l)
for(int c=1;c<=l;c++) {
f[i][j][k][l]+=f[i-1][0][0][c-1]*f[i][j][k][l-c];
f[i][j][k][l]%=mod;
}
}
int ans=f[d][l1][l2][l3];
if(d) ans-=f[d-1][l1][l2][l3];
printf("%d\n",(ans%mod+mod)%mod);
return 0;
}
如果各位感觉我码风丑陋,不妨看一看 XuHt 大佬的代码:
#include<bits/stdc++.h>
using namespace std;
const int mod = 11380;
int f[31][11][11][11], L1, L2, L3, D;
int main() {
cin >> L1 >> L2 >> L3 >> D;
for (int i = 0; i <= D; i++) f[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++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][p - 1][q][r] * f[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++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][q - 1][r] * f[i][j][k - q][l - r]) % mod;
}
if (l > 0) { // 第一段最外层是()
for (int r = 1; r <= l; r++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][0][r - 1] * f[i][j][k][l - r]) % mod;
}
}
cout << (f[D][L1][L2][L3] - (D ? f[D - 1][L1][L2][L3] : 0) + mod) % mod << endl;
}
AcWing《Linux基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/57/group_buy/25280/