题意
构造 L1对{},L2对[],L3对() 组成的深度为D的括号序列,求方案数。
注:中括号里不能有大括号,小括号里不能有中括号和大括号。
计数类DP
初步想法
希望把构造的序列变成规模更小的子问题
有 {} [] () 和 +(连接) 四种方式
但注意 ABC
有 A+BC
和 AB+C
两种构造方式,需要避免重复计数
解题原则
计数类DP需要关注“基准点”,围绕“基准点”构造一个不可分割的整体
通常以“第一XXX”作为基准点
——《算法竞赛进阶指南》
本题思路
这里就是考虑“第一段”括号序列(它作为一个整体,只能是{} [] 或 (),不能是+)
即划分成 {A}B
、[A]B
或 (A)B
,其中 A,B 是子问题,即可避免重复
例如:
[[()]()]{{[](())}}{[()]}
有三段 [[()]()]
{{[](())}}
{[()]}
按照我们的思路,它划分子问题的方式是唯一的:
[___A__]_______B________
[[()]()]{{[](())}}{[()]}
这样就可以不重不漏。
动规设计
f[i,j,k,l]表示深度为i,由j对{},k对[],l对()组成的括号序列数量
转移:
枚举第一段的最外层括号
枚举第一段的深度、三种括号数
例如[[()]()]{{[](())}}{[()]}
是f[4,3,4,5]
子问题A部分,即[()]()
,为f[2,0,1,2]
子问题B部分,即{{[](())}}{[()]}
,为f[4,3,2,3]
更优秀的做法
我们没有必要枚举每一段的确切深度。
可以用f[i,j,k,l]表示深度不超过i,由j对{},k对[],l对()组成的括号序列数量。
最终答案变为 f[D,L1,L2,L3] - f[D-1,L1,L2,L3]
转移简化为:
枚举第一段的最外层括号
枚举第一段的三种括号数
以中括号为例:
f[i,j,k,l] += Σq Σr (f[i-1][0][q-1][r] * f[i][j][k-q][l-r])
第一段最外层是中括号,所以A部分子问题不能再有大括号,还有q-1个中括号和r个小括号,深度<=i-1(因为进入了一层)
剩余的括号都由B部分子问题构成
初值:f[0~D,0,0,0]=1,其余为0
时间复杂度
O(D*L^6)
C++ 代码
#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;
}
😩
%%%
膝盖软了
生猛的
for
循环(stO Lyd老师 Orz