有一个括号序列，你可以选择两个位置i，j（i可以等于j），进行交换。使得最后的循环位置（i的数目）最大。
循环位置：i（0<=i<len），将前i个字符移到最后，得到的新序列是合法的括号序列。
这题还有个大数据范围版本，那题思路太神仙了，我等凡人就学学暴力吧！这题有个结论，假设)为-1，(为+1，那么一个括号序列的循环匹配个数等于前缀和最小值的个数。证明参考某大佬的：
假设对于序列)()(，它的前缀和是-1 0 -1 0
当上述前缀值<0时，这个前缀序列一定是不合法的。然后考虑什么时候把括号序列的一段前缀移到后面去是合法的。
首先你需要使得移动之后，前面的括号序列合法。也就是说你得把一段“连续的极长非合法前缀”找出来（对于样例是)）。这个东西恰好在前缀和第一次取得最小值时取得（前缀和取-1）。然后实际上你还可以在这个前缀后面接上一些“本身合法”的括号序列，像这样：)()。后面那个合法的序列对答案没有影响，因此循环移位的数量就是前缀和最小值的数量。
然后我们就可以O（n^3）暴力啦！
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int n;
string s;
int solve()
{
int sum=0,mi=0,cnt=0;
for(int i=0; i<n; i++)
{
if(s[i]==‘(‘)
cnt++;
else
cnt--;
mi=min(cnt,mi);
}
cnt=0;
for(int i=0;i<n;i++)
{
if(s[i]==‘(‘)
cnt++;
else
cnt--;
if(cnt==mi)
sum++;
}
return sum;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>s;
int cnt=0;
for(int i=0; i<n; i++)
{
if(s[i]==‘(‘)
cnt++;
else
cnt--;
}
if(cnt)
{
cout<<"0\n1 1"<<endl;
return 0;
}
int ans=solve();
int l=1,r=1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
swap(s[i],s[j]);
int tmp=solve();
if(tmp>ans)
{
l=i,r=j;
ans=tmp;
}
swap(s[i],s[j]);
}
}
cout<<ans<<endl;
cout<<l+1<<" "<<r+1<<endl;
return 0;
}
原文：https://www.cnblogs.com/mcq1999/p/11837943.html