题意:
给定一个括号串。若把子串 \([1,i]\) 换到子串 \([i+1,n]\) 的后面,得到的新串合法,则称 \(i\) 为一个特殊位置。
现在交换两个位置,问交换哪两个位置可使特殊位置最多。
串长 500
思路:
n^2 枚举位置进行交换,然后 \(O(n)\) 数特殊位置数:
求括号串的平衡前缀数组,即把左括号看成 1,右括号看成 -1,然后做前缀和。
首先总左括号数要等于总右括号数,即 \(s_n=0\),否则答案是 0。
如果我们把子串 \([1,i]\) 换到子串 \([i+1,n]\) 的后面,那么 \(s[i+1,n]\) 要消除 \(s[1,i]\) 的影响,即 \(s[i+1,n]\) 中的所有 \(s\) 减去 \(s_i\);
然后 \(s[1,i]\) 放到后面后,要加上 \(s[i+1,n]\) 的影响,即 \(s[1,i]\) 中的所有 \(s\) 加上 \(s_n\)。注意到经过上一步后,这个 \(s_n=-s_i\),所以这步操作也是把 \(s[1,i]\) 中的所有 \(s\) 减去 \(s_i\)
综上,就是要把所有数减去 \(s_i\) 。
众所周知,括号序列合法要求所有前缀和非负,所以特殊位置只能取 \(s_i\) 最小的 \(i\)
所以每次数最小的 \(s_i\) 的有几个即可
const signed N = 503; int n, s[N], ans, l=1, r=1; char a[N]; int cal() { for(int i = 1; i <= n; i++) s[i] = s[i-1] + (a[i] == '(' ? 1 : -1); if(s[n]) return 0; int mn = *min_element(s+1, s+1+n), cnt = 0; for(int i = 1; i <= n; i++) cnt += s[i] == mn; return cnt; } signed main() { iofast; cin >> n >> a + 1; for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) { swap(a[i], a[j]); int res = cal(); if(ans < res) ans = res, l = i, r = j; swap(a[i], a[j]); } cout << ans << endl << l << ' ' << r; }