自动搬运

查看原文

来自洛谷，原作者为

	Zjl37 I could call myself a programmer no matter how little I know (0275.)

搬运于2025-08-24 22:00:12，当前版本为作者最后更新于2021-07-13 10:58:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单的动态规划可以完成第一问

从上往下进行动态规划。设 $f(i, j, k)$ 为到达第 $i$ 行第 $j$ 列，$\text{\small\sf 右括号数}-\text{\small\sf 左括号数} = k$ 时序列的最大长度。

合法括号序列的性质：

任何后缀中 $\text{\small\sf 右括号数}-\text{\small\sf 左括号数} \ge 0$，因此我们要求 DP 中 $k\ge 0$。

优化空间的提示：

由于最终左右括号数量相等，所以 k 可以只用开 R 的一半。

DP 的起点可以是第一行非左括号的位置或炸弹的位置。对于第一行的右括号，k = 1，f 赋值为 1；对其他起点，k = 0，f 赋值为 0；

对其他位置，初始化时可以赋值一个负数。

从 $f(i, j, k)$ 可以转移到下一行的三个相邻位置。根据下一个位置的字符，k 发生相应的变化。比如接收到一个左括号，则 k 减一。如果接收到的是括号，f 的值就加 1。

最终的答案即为 $f(R, \textsf{‘M’\small所在的横坐标}, 0)$。

记录节点状态以求出字典序最小的括号序列

我们发现，如果用滚动数组优化，完全有足够的空间用二进制压缩地记录下每一个 DP 状态的括号序列!

于是我们在 DP 时不仅比较长度，而且在长度相等时留意一下序列大小即可。

该算法的时间复杂度是 $\mathcal O(R^2 S)$，用到的空间不到 5MB，真是惊人的小！

参考实现

本题的代码非常的琐碎，请仔细阅读。

#include <bits/stdc++.h>
using namespace std;
#define validx(a) ((a) >= 1 && (a) <= s)
int r, s, sx;
char c[301][301];

// 一个 node 代表 DP 的一个状态
struct node {
	int len;
	unsigned seq[10];
	// seq 记录括号序列，每个二进制位上 0 代表 '('，1代表 ')'
	// 用 10 个 32 位整数可以存下至多 320 个括号。
	// 不用 std::bitset，因为它没有提供比较运算符。

	void init(int x, unsigned y) {
		len = x;
		memset(seq, 0, sizeof seq);
		seq[0] = y;
	}
	void set(unsigned x) {
		seq[x/32] |= 1u<<x%32;
	}
} nd[2][301][152];

// 比较括号序列的大小。
bool cmpSeq(const node &a, const node &b) {
	for(int i = (a.len-1)/32+1; i >= 0; --i) {
		if(a.seq[i] != b.seq[i]) return a.seq[i] < b.seq[i];
	}
	return 0;
};

ostream &operator<<(ostream &out, const node &x) {
	out<<x.len<<"\n";
	for(int i = x.len-1; i >= 0; --i)
		out<<(x.seq[i/32] & 1u<<i%32 ? ')' : '(');
	return out;
}

int main() {
	// ifstream cin("r:/test/retro.in");
	ios::sync_with_stdio(0);
	cin>>r>>s;
	memset(nd, -1, sizeof nd);
	for(int i = 1; i <= r; i++)
		for(int j = 1; j <= s; j++) {
			cin>>c[i][j];
		}
	// sx = 'M' 所在的横坐标
	sx = find(c[r]+1, c[r]+s+1, 'M') - c[r];
	for(int j = 1; j <= s; j++)
		if(c[1][j] == ')') {
			nd[1][j][1].init(1, 1);
		} else if(c[1][j] != '(') {
			nd[1][j][0].init(0, 0);
		}
	// 将 DP 转移中大量重复的代码写成函数，节省码量。
	// 注意：为了方便，这个函数中没有向 seq 添加新的括号。
	auto dpUpt = [](const node &cur, node &nxt, int df) -> bool {
		if(cur.len+df > nxt.len || (cur.len+df == nxt.len && cmpSeq(cur, nxt))) {
			nxt = cur;
			nxt.len = cur.len+df;
			return 1;
		}
		return 0;
	};
	for(int i = 1; i < r; ++i) {
		// 及时清空滚动数组。
		memset(nd[i+1 & 1], -1, sizeof nd[0]);
		for(int j = 1; j <= s; j++) {
			// 注意：非首行的炸弹作为起点，只能在滚动到此时进行初始化。
			if(c[i+1][j] == '*') nd[i+1 & 1][j][0].init(0, 0);
			// 只处理序列存在的节点。
			for(int k = 0; k <= r/2 && k <= i; ++k) if(nd[i & 1][j][k].len >= 0) {
				// 注意：为了方便，在新一轮 DP 开始前向 seq 中添加括号。
				// 因为二进制用 0 代表左括号，所以只用管右括号。
				if(c[i][j] == ')') {
					nd[i & 1][j][k].set(nd[i & 1][j][k].len-1);
				}
				for(int dx: {-1, 0, 1}) if(validx(j+dx)) {
					if(c[i+1][j+dx] == ')') {
						dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k+1], 1);
					} else if(c[i+1][j+dx] == '(') {
						if(k > 0)
							dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k-1], 1);
					} else if(c[i+1][j+dx] != '*') {
						dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k], 0);
					}
				}
			}
		}
	}
	cout<<nd[r & 1][sx][0]<<endl;
	return 0;
}