bracket

题面

#3543. 「CSP-S 2021」括号序列 - 题目 - LibreOJ (loj.ac)

简单翻译一下，就是这个意思。

• (S) 是合法的括号序列，其中 \(S\) 是一个不超过 \(k\) 个的连续 * 号（可以为 \(0\) 个）。
• A、B 是合法的序列，那么 ASB 是一个合法的括号序列。
• 如果 A 是合法的序列，那么 (SA) 或者是 (AS) 均合法。

统计一下这样合法的括号序列的个数。给定你一些原本的固定的括号，剩下的 ? 可以随便变。

数据范围 \(n\le 500\)

题解

首先这道题明显就是个动态规划。

考试的时候想了很多方法，这里说一下一些错误的方法。

令 \(f_{i,j,k}\) 表示做到第 \(i\) 个位置，有 \(j\) 个括号，有 \(k\) 个连续的 * 的合法方案数量。这玩意明显不对，因为可能会统计出来类似于 (SAS) 的串，经过修改之后也发现这方法没什么前途。

经过思索不难发现正常的dp肯定不是解决方法，数据范围 \(n\le 500\) 其实给了提示，那么大概需要一个 \(O(N^3)\) 的做法。

考虑区间dp即可。感觉这题就是在考验 dp 的基本功。

我们令 \(f_{i,j}\) 为 \([i,j]\) 区间成为合法括号序列的方案数，而 \(g_{i,j}\) 表示 \([i,j]\) 区间成为合法括号序列，并且形如 (X) 其中最左边和最右边的括号是配对的，再令 \(s_{i,j}\) 表示 SA 类的不一定合法的字符串。至于为什么这么转移的话，刚开始我是只想转移 \(f_{i,j}\) 的，但是发现这样会重复，于是不得已采取的这个方法。

那么就有一个转移套转移的方程。我们考虑刚开始 \(O(nK)\) 的预处理出来一些形如 (S) 的 \(f_{i,j}\) 和 \(g_{i,j}\)。然后通过这些基本括号串将一些 \(g_{i,j}\) 处理出来。

那么我们的转移方程是

这两个要求 \(s_i='('\) 且 \(s_j=')'\)，其中 \(s[i:j]\) 表示 \(s\) 的 \(i\) 位置到 \(j\) 位置的子串。而 \("*"\) 表示一个合法的 \(S\) 串。

\(f_{i,j}=f_{i+1,j-1}+\sum_{k1=i+1}^{j-2} g_{i,k1}\times s_{k1,j}+\sum_{k1=i+1}^{i+K}[s[i+1:k1]="*"]f_{k1+1,j-1}+\sum_{k1=j-K}^{j-1}[s[k1:j-1]="*"]f_{i+1,k1-1}\)

\(g_{i,j}=f_{i+1,j-1}+\sum_{k1=i+1}^{i+K}[s[i+1:k1]="*"]f_{k1+1,j-1}+\sum_{k1=j-K}^{j-1}[s[k1:j-1]="*"]f_{i+1,k1-1}\)

这个无要求

\(s_{i,j}=\sum_{k1=i}^{i+K}[s[i:k1-1]="*"]f_{k1,j}\)

我们可以用刷表的方式省去算 \(s_{i,j}\) 的枚举。然后基本就没啥了。

主要就是个dp的想法，只要想到了，这题就迎刃而解了。

#include 
using std::cin;
using std::cout;
using std::set;
using std::map;
using std::sort;
using std::pair;
using std::vector;
const int N = 505, mod = 1e9 + 7;
inline int Mod(int x) {
	if (x < 0) {
		return x + mod;
	}
	else if (x >= mod) {
		return x - mod;
	}
	else {
		return x;
	}
}
int n, K, sum[N], f[N][N], g[N][N], p[N][N];
char s[N];
inline bool isl(int pos) {
	return s[pos] == '(' || s[pos] == '?';
}
inline bool isr(int pos) {
	return s[pos] == ')' || s[pos] == '?';
}
inline bool isx(int pos) {
	return s[pos] == '*' || s[pos] == '?';
}
int main() {
	freopen("bracket.in", "r", stdin);
	freopen("bracket.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> K >> s + 1;
	for (int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + (s[i] == '?' || s[i] == '*');
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n && j <= i + K + 1; ++j) {
			p[i][j] = f[i][j] = isl(i) && isr(j) && (sum[j - 1] - sum[i] == (j - i - 1));
		}
	}
	for (int i = 1; i < n; ++i) {
		if (f[i][i + 1]) {
			g[i][i + 1] = f[i][i + 1];
			for (int j = i - 1; j >= 1 && j >= i - K; --j) {
				if (isx(j)) {
					g[j][i + 1]++;
				}
				else {
					break;
				}
			}
		}
	}
	for (int l = 3; l <= n; ++l) {
		for (int i = 1; i <= n - l + 1; ++i) {
			int j = i + l - 1;
			if (isl(i) && isr(j)) {
				for (int k1 = i + 1; k1 <= j - 2; ++k1) {
					f[i][j] = Mod(f[i][j] + 1LL * p[i][k1] * g[k1 + 1][j] % mod);
				}
				f[i][j] = Mod(f[i][j] + f[i + 1][j - 1]);
				p[i][j] = Mod(p[i][j] + f[i + 1][j - 1]);
				for (int k1 = i + 1; k1 < j - 2 && k1 <= i + K; ++k1) {
					if (isx(k1)) {
						f[i][j] = Mod(f[i][j] + f[k1 + 1][j - 1]);
						p[i][j] = Mod(p[i][j] + f[k1 + 1][j - 1]);
					}
					else {
						break;
					}
				}
				for (int k1 = j - 1; k1 >= i + 3 && k1 >= j - K; --k1) {
					if (isx(k1)) {
						f[i][j] = Mod(f[i][j] + f[i + 1][k1 - 1]);
						p[i][j] = Mod(p[i][j] + f[i + 1][k1 - 1]);
					}
					else {
						break;
					}
				}
				g[i][j] = Mod(g[i][j] + f[i][j]);
				for (int k1 = i - 1; k1 >= 1 && k1 >= i - K; --k1) {
					if (isx(k1)) {
						g[k1][j] = Mod(g[k1][j] + f[i][j]);
					}
					else {
						break;
					}
				}
			}
		}
	}
	cout << f[1][n] << '\n';
	return 0;
}

同步发布于 siriehn_nx - 博客园 (cnblogs.com)