题目链接
题意
关于 合法的括号序列 有如下几个定义：
1. 空序列是一个合法的括号序列；
2. 如果 s 是一个合法的括号序列，那么 (s) 也是；
3. 如果 s 和 t 都是合法的括号序列，那么 st 也是。
现定义一个仅包含 ('(')， (')') 和 ('?') 字符的字符串为优美的 当且仅当：
存在一种方法将所有的 ('?') 用 ('(') 或 (')') 替换，从而得到一个合法的括号序列。
题解
法一：官方题解
结论：
一个仅包含 ('(')， (')') 和 ('?') 字符的字符串为优美的 当且仅当：
- (|s|) is even.
- (0 ≤ s[1..i].count('(') + s[1..i].count('?') - s[1..i].count(')')) for each (1 ≤ i ≤ |s|).
- (0 ≤ s[i..|s|].count(')') + s[i..|s|].count('?') - s[i..|s|].count('(')) for each (1 ≤ i ≤ |s|).
证明：
暂略
复杂度：
做法：枚举左端点，右端点从左至右，(f[l][r]) 表示 (s[l..r]) 满足第二个条件；枚举右端点，左端点从右至左，(g[l][r]) 表示 (s[l..r]) 满足第三个条件；枚举长度与左端点，判断哪些段既满足条件 (2) 又满足 条件 (3)
时间：(O(N^2))
空间：(O(N^2))
法二：参考mouse_wireless的comment
回顾
回顾一下，如果没有问号，我们是怎么判断一个合法的括号序列的？
设一个计数器 (cnt)，从左至右扫描，遇到 ('(') 就加一，遇到 (')') 就减一。
则括号序列合法 当且仅当：
- (cnt) 中途不曾出现负值；
- (cnt) 最后为0
衍伸
如果有了问号呢……？
那就设两个计数器，一个 (cnt) 含义与上相同，另一个 (qmk) 记录问号的数目。
在扫描过程中：
- 首先显然的，(cnt) 在任意时刻依然不能容许为负值；
- 一旦某一时刻 (cnt==qmk)，则此时所有的 (qmk) 都可被用作右括号，于是便可以得到一个合法的括号序列，(++ans)；
- 如果某一时刻 (cnt<qmk)，此时若所有的 (qmk) 都被用作右括号，则会导致右括号偏多，无法构成一个合法的括号序列，更无法推进下去。所以，此时 必须 将 (qmk) 匀 一个 出来作为左括号，才可以继续推进。（因为在没(break)出去之前始终有(cntgeq qmk) (holds)，所以在下一个扫描更新的时候，(qmk) 最多只会比 (cnt) 多(1)，所以只需匀一个）
复杂度
做法：枚举左端点，右端点从左至右扫描，如上所述维护两个计数器。
显见，时间是法一的 (1/3)，我的代码分别是跑了 (218ms) 和 (61ms)
时间：(O(N^2))
(额外)空间：(O(1))
Code
Ver. 1
#include <bits/stdc++.h>
#define maxn 5010
using namespace std;
typedef long long LL;
bool f[maxn][maxn], g[maxn][maxn];
char s[maxn];
int main() {
scanf("%s", s);
int len = strlen(s);
for (int l = 0; l < len; ++l) {
int cnt = 0;
for (int r = l; r < len; ++r) {
cnt += s[r]==')' ? -1 : 1;
f[l][r] = cnt >= 0;
if (!f[l][r]) break;
}
}
for (int r = len-1; r >= 0; --r) {
int cnt = 0;
for (int l = r; l >= 0; --l) {
cnt += s[l]=='(' ? -1 : 1;
g[l][r] = cnt >= 0;
if (!g[l][r]) break;
}
}
int ans=0;
for (int i = 2; i <= len; i += 2) {
for (int s = 0; s <= len-i; ++s) {
int t = s+i-1;
if (f[s][t] && g[s][t]) ++ans;
}
}
printf("%d
", ans);
return 0;
}
Ver. 2
#include <bits/stdc++.h>
#define maxn 5010
using namespace std;
typedef long long LL;
char s[maxn];
int main() {
scanf("%s", s);
int len = strlen(s), ans=0;
for (int l = 0; l < len; ++l) {
int cur = 0, qmk = 0;
for (int r = l; r < len; ++r) {
if (s[r] == '(') ++cur;
else if (s[r] == ')') --cur;
else ++qmk;
if (cur < 0) break;
if (cur < qmk) ++cur, --qmk;
if (cur == qmk) ++ans;
}
}
printf("%d
", ans);
return 0;
}
反思
昨晚比赛时，看了五分钟觉得是个 (dp)，(WA) 了一发后（...）想清楚了正确的转移：
(s[st..ed]) 为合法的括号序列 当且仅当 下面两个条件中的任意一个成立：
- (s[st+1..ed-1]) 为合法的括号序列，
并且 (s[st]!=')')，并且 (s[ed]!='(') - (exists i)，(s[st,i]) 与 (s[i+1,ed]) 均为合法的括号序列
然而这是 (O(N^3)) 的转移。莽了一发，显然 (T) 了。
接下来就各种挖空心思优化，分别记录每个点作为右端点能匹配上哪些合法括号序列的左端点，以及作为左端点能匹配上哪些合法括号序列的右端点，借助这些信息，用已知的合法括号序列来推，还是 (T) 了，很绝望（并不很明白为什么 (Orz)
今天看题解，看到结论，再看到一长串证明，心情很是复杂，想了想觉得可能也是可以猜出来的？又开始恍惚地感叹直觉的重要（
然后就往下看到了 (comment)，觉得，多画几个例子多联想回顾，这种做法当真是可以想出来的。昨天还是陷在 (dp) 里了。
// 发觉自己现在有一种倾向
// 写着写着博客就认为自己是能够想出来的
// 噫吁嚱