本文共 915 字，大约阅读时间需要 3 分钟。

【题解】

恐怕这道题最大的难点在于....读题

题意：给定一个长度为n的(n<=500)括号序列，给一个交换两个位置上元素的机会(不一定要不同)，询问平移不同长度(从后往前平移)使得整个序列成为一个完美序列(每个'('有一个对应的')')的最多可能长度数目。比如

S：)(())()()(()

1.(())(())()()   2.()(())(())()  3.()()(())(())  4.(())()()(()) 

思路：n不大，我们完全可以用枚举两个位置和整个序列位置O(n^3)的暴力求法。在这里注意，对于一个括号序列，如果我们把'('赋值1，把')'赋值-1，那么很显然，一个完美序列的整个前缀和必定为0；换句话说，如果整个括号序列的权值和为0那么一定可以通过平移得到至少一个完美的括号序列。

我们考虑到我们需要平移的这个括号序列，一定是中间完美(或者没有中间)，两边都不完美(或者都完美)的这个样子，所以我们需要找到一定要凑在一起的括号子序列，这是一种，剩下的不影响的所有完美子序列可以依次累加，比如上面这个例子(自己看)。由于，对于一个完美括号序列来说，不管是什么时候，‘('的数目都会大于等于')’的数目，所以前缀和必定大于等于0，每当出现一个0就说明又完成了一个完美序列。那么我们推广一下，若是两个位置的前缀和相同(也就是差值为0)，那么这两个位置之间(前开后闭)一定是一个完美序列。但是这两个位置不是什么随便的位置，必须是')'所在的位置，因为一个完美序列结尾一定是')'嘛~所以我们以一个序列的最小值作为比较的值即可。

【代码】

#include 
   
    using namespace std;const int maxn=505;int n,x=1,y=1,ans;char s[maxn];int main(){    scanf("%d%s",&n,s+1);    for(int i=1;i
    
     ans) ans=c,x=i,y=j;            swap(s[i],s[j]);        }    }	printf("%d\n%d %d\n",ans,x,y);}
    
   

转载地址：http://thfen.baihongyu.com/