題意
有一個括號序列，你可以選擇兩個位置i，j（i可以等于j），進行交換，使得最后的回圈位置（i的數目）最大，
回圈位置：i（0<=i<len），將前i個字符移到最后，得到的新序列是合法的括號序列，
- )()()( 的回圈位置有 1、3、5
- )((()))( 的回圈位置有 1、7
思路
這題還有個大資料范圍版本，那題思路太神仙了，我等凡人就學學暴力吧！這題有個結論，假設)為-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.uj5u.com/qita/127166.html
標籤：其他