括号序列

brackets.c/cpp/pas

（2s/256M）

【题目描述】

课堂上，Felix刚刚学习了关于括号序列的知识。括号序列是一个只由左括号“(”和右括号“)”构成的序列；进一步的，一个合法的括号序列是指左括号和右括号能够一一匹配的序列。

如果用规范的语言说明，一个合法的括号序列可以有以下三种形式：

1 S=“”（空串），S是一个合法的括号序列；

2 S=XY，其中X，Y均为合法的括号序列，则S也是一个合法的括号序列；

3 S=(X)，其中X为合法的括号序列，则S也是一个合法的括号序列。

这时老师在黑板上写出了一个了括号序列：“()))()”。

Felix一眼就看出这个序列并不是合法的括号序列。

这时老师提出了一个这样的问题：能否在序列中找出连续的一段，把这一段里面的左括号变成右括号，右括号变成左括号，变换之后整个序列可以变成合法的呢？

Felix想到，可以把[3..5]进行调换，这样序列就会变为()(())，是一个合法的序列。很明显，不止有一种方法可以使整个序列变合法。

这时，老师又在黑板上写出了一个长度为N的括号序列。Felix想，能否对这个序列进行至多一次变换，使它变合法呢？

【输入格式】brackets.in

第一行一个整数T，代表数据的组数；接下来T行，每一行一组数据。

每组数据一行，代表给出的括号序列。

【输出格式】brackets.out

输出共T行，对于每组数据，输出“possible”（可以变换）或“impossible”（不可变换）。（不含引号）

【样例输入】

()))

)))(

()

【样例输出】

possible

impossible

possible

【数据范围与约束】

对于50%的数据，T<=5, N<=20;

对于100%的数据，T<=10, N<=5000.

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5005;
int n;
int a[N];
int f[2][N][3];
string s;
void first()
{
    cin>>s;
     n=s.size();
    for(int i=0;i<n;i++)
    if(s[i]=='(')    a[i]=1;
    else a[i]=-1;    
}
void work()
{
    memset(f,0,sizeof f); 
    f[0][0][0]=1;
    bool pre=0;
    for(int i=0;i<n;i++)
    {
        memset(f[!pre],0,sizeof f[!pre]);
        for(int j=0;j<=i&&i+j<=n;j++)
        {
            if(f[pre][j][0])
            {
                if(a[i]<0&&j>0)    f[!pre][j-1][0]=1;
                else if(a[i]>0) f[!pre][j+1][0]=1;
                
                if(a[i]>0&&j>0) f[!pre][j-1][1]=1;
                else if(a[i]<0) f[!pre][j+1][1]=1;
            }
            if(f[pre][j][1])
            {
                if(a[i]>0&&j>0)    f[!pre][j-1][1]=1;
                else if(a[i]<0)    f[!pre][j+1][1]=1;
                
                if(a[i]<0&&j>0)    f[!pre][j-1][2]=1;
                else if(a[i]>0) f[!pre][j+1][2]=1;                
            }
            if(f[pre][j][2])
            {
                if(a[i]<0&&j>0)    f[!pre][j-1][2]=1;
                else if(a[i]>0) f[!pre][j+1][2]=1;            
            }
            
        }
        pre=!pre;
    }
    int  ok=  f[pre][0][0] | f[pre][0][1] | f[pre][0][2];
    if(ok) printf("possible
");
    else printf("impossible
");
    return ;
}
int  main()
{
    freopen("brackets.in","r",stdin);
    freopen("brackets.ans","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        first();
        work();
    }
    return 0;
}