题解 | #删括号#

突然做到这题，心血来潮写个题解。

首先把题目条件放宽，也就是允许 和 是非法括号序列，例如 )))((())) 和 )))。

然后考虑 ，设 表示是否存在一种方案，使得 的前 个字符通过删除一些 () 和 的前 个字符完全相同。

• 若 ，那么这个最后的字符可以不用考虑，即 。

• 若 ，考虑删除以 结尾的一个最短合法括号序列，得到下标 ，那么 。但是删除有可能非法，接下来考虑什么情况是合法的。由于合法括号序列反着看也是合法的（左右括号的地位 交换 一下），所以可以从 开始往左统计 右括号数量与左括号数量之差，记为 ，一旦 就退出，且只有 才更新状态。

关于初始化的问题：除了 ，对于任意一个 的前缀，若其是合法括号序列，也要初始化 ，表示可以把这个前缀删至空串。

C++ 代码

#include <bits/stdc++.h>

using LL = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	
    std::string s, t;
    std::cin >> s >> t;
    
    int n = s.size();
    int m = t.size();
    
    std::vector f(n + 1, std::vector(m + 1, false));
    f[0][0] = true;
    
    for (int i = 0, cnt = 0; i < n and cnt >= 0; i += 1) {
        cnt += s[i] == '(' ? 1: -1;
        if (cnt == 0) {
            f[i + 1][0] = true;
        }
    }
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            if (s[i] == t[j]) {
                f[i + 1][j + 1] = f[i][j];
            }
            int cnt = 0, k = i;
            while (k >= 0) {
                cnt += s[k--] == ')' ? 1: -1;
                if (cnt <= 0) {
                    break;
                }
            }
            if (cnt == 0 and f[k + 1][j + 1]) {
                f[i + 1][j + 1] = true;
            }
        }
    }
    std::cout << (f[n][m] ? "Possible": "Impossible") << "\n";
    
    return 0;
}

造的几个例子：

Case1

Input1:

))()))
))))

Output1:

Possible

Case2

Input2:

(())))
))

Output2:

Possible

Case3

Input3:

)))((()))
)))

Output3:

Possible

Case4

Input4:

()(()
(

Output4:

Possible

Case5

Input5:

)))))
))

Output5:

Impossible

Case6

Input6:

(())
))

Output6:

Impossible