CF1238D1
题意
如果一个括号串是匹配的,我们认为它是正确的.
给你一个长度为n的字符串,让你可以交换这个字符串中的任意两个(自己和自己交换也可以).定义ans为有多少种位移方法使得串是正确的?
要求输出ans的最大值.
(位移位数k满足$0<=k<n$)
$1<=n<=500$
思路
这个题其实并不难,一开始的思路想复杂了.
首先我们统计一下括号串的左右括号的个数分别是多少,如果不相同,那么ans一定是0.
接下来的情况就是括号串在括号个数上一定是匹配的
首先发现这个题$O(n^3)$是可以通过的,所以我们考虑$O(n^2)$枚举交换的两点,然后每次枚举之后考虑如何$O(n)$求出对于一个字符串的ans.
我们可以这样考虑: 先看一个正确的串有什么性质.
一个正确的串可以分成好几部分,每个部分都是不可分割的正确串
例如()()(())就是一个为ans为3的串
我们可以令左括号为1,右括号为-1,统计一下前缀和
我们发现它的前缀为10101210,恰好有三个零
我们发现在一个不可分割的正确串中,只会在末尾有零.(由于前文发现左右括号个数是相等的,所以最后一位一定是0)
也就是我们只要找到一个正确的位移数,使得串由几个正确串拼接而成,然后统计0的数量就可以了.
由以前做题的经验可以得知,在一个括号串中除去已经匹配的正确串,得到的一定是形如)))))(((((的串,我们只需要将前面的右括号全部塞到末尾即可.
当然,这堆右括号中或许掺杂着正确串,由于正确串并不会影响其后的前缀和,所以我们只需要找到最后一个右括号的位置就可以了,它所在的前缀和一定是整个序列前缀和的最小值.
其实问题到这里就已经解决了.我采取的做法是,找到前缀和的最小值后,让所有的前缀和(其实到这里就是数组的值了,前缀和只在第一次的时候求,然后就固化为数组的值)都加这个最小值的相反数.对于右括号来说,就相当于将左括号塞到了他们前头,每个括号都要加左括号的数量(也就是最小值的相反数),对于左括号来说,相当于前面少了一堆右括号.这里的处理方法见仁见智,只要能想到把右括号塞到后面就可以.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
string s;
int a[510];
int work() {
int minn = 0;
int pre = 0;
for (int i = 0; i < n; ++i) {
a[i] = pre;
if (s[i] == '(') {
++a[i];
} else {
--a[i];
}
pre = a[i];
minn = min(pre, minn);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
a[i] += -minn;
if (a[i] == 0) {
++ans;
}
}
return ans;
}
int main() {
cin >> n >> s;
int c1 = 0, c2 = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(')
++c1;
if (s[i] == ')')
++c2;
}
if (c1 != c2) {
printf("0\n1 1\n");
} else {
int ans = work();
// printf("ans = %d\n", ans);
int id1 = 1, id2 = 1;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (s[i] != s[j]) {
swap(s[i], s[j]);
int tmp = work();
if (ans < tmp) {
ans = tmp;
id1 = i, id2 = j;
}
swap(s[i], s[j]);
}
}
}
printf("%d\n%d %d\n", ans, id1 + 1, id2 + 1);
}
return 0;
}
