Codeforces Round #288 (Div. 2) E. Arthur and Brackets [dp 贪心]

Notice that the memory limit is non-standard.

Recently Arthur and Sasha have studied correct bracket sequences. Arthur understood this topic perfectly and become so amazed about correct bracket sequences, so he even got himself a favorite correct bracket sequence of length 2n. Unlike Arthur, Sasha understood the topic very badly, and broke Arthur's favorite correct bracket sequence just to spite him.

All Arthur remembers about his favorite sequence is for each opening parenthesis ('(') the approximate distance to the corresponding closing one (')'). For the i-th opening bracket he remembers the segment [l_i, r_i], containing the distance to the corresponding closing bracket.

Formally speaking, for the i-th opening bracket (in order from left to right) we know that the difference of its position and the position of the corresponding closing bracket belongs to the segment [l_i, r_i].

Help Arthur restore his favorite correct bracket sequence!

Input

The first line contains integer n (1 ≤ n ≤ 600), the number of opening brackets in Arthur's favorite correct bracket sequence.

Next n lines contain numbers l_i and r_i (1 ≤ l_i ≤ r_i < 2n), representing the segment where lies the distance from the i-th opening bracket and the corresponding closing one.

The descriptions of the segments are given in the order in which the opening brackets occur in Arthur's favorite sequence if we list them from left to right.

Output

If it is possible to restore the correct bracket sequence by the given data, print any possible choice.

If Arthur got something wrong, and there are no sequences corresponding to the given information, print a single line "IMPOSSIBLE" (without the quotes).

Sample test(s)

Input

Output

()()()()

Input

Output

((()))

Input

Output

IMPOSSIBLE

Input

Output

(())()

一把一把的泪啊，，，看错题搞了很久，，，然后dp时输出串也搞了很久，，，原来水水的贪心就能过，，，泪流满面，

转一下贪心的思路： http://www.cnblogs.com/wuyuewoniu/p/4256013.html

CF上给这道题打了dp和greedy两个标签，应该是两种做法都可以吧。下面说贪心的做法。

题意：

有一些配好对的括号，现在已知第i对括号，左右括号的距离在[L_i, R_i]区间中。按照左括号出现的顺序编号。

输出原括号序列。

分析：

因为括号是以栈的形式配对的，所以我们将这些区间也以栈的形式存储。

假设第i对括号的左括号在位置p，则右括号只能在[p+L_i, p+R_i]这个区间中。

每放一个左括号，就将右括号对应的区间入栈。

贪心的办法是，如果当前位置位于栈顶区间的范围内，则尽早入栈。

贪心的理由是：因为早点使栈顶的括号配对，就有更大的机会使栈顶的第二队括号配上对。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 #include<map>
  9 #include<set>
 10 #include<stack>
 11 #include<string>
 12 
 13 #define N 1205
 14 #define M 105
 15 #define mod 1000000007
 16 //#define p 10000007
 17 #define mod2 1000000000
 18 #define ll long long
 19 #define LL long long
 20 #define eps 1e-6
 21 #define inf 100000000
 22 #define maxi(a,b) (a)>(b)? (a) : (b)
 23 #define mini(a,b) (a)<(b)? (a) : (b)
 24 
 25 using namespace std;
 26 
 27 int n;
 28 char s[N];
 29 int l[N],r[N];
 30 int flag;
 31 int dp[605][605];
 32 
 33 void ini()
 34 {
 35     memset(dp,-1,sizeof(dp));
 36     int i;
 37     for(i=1;i<=n;i++){
 38         scanf("%d%d",&l[i],&r[i]);
 39     }
 40     flag=0;
 41     s[2*n]='\0';
 42 }
 43 
 44 int fun(int now,int tot,int st,int en)
 45 {
 46    // printf("now=%d tot=%d st=%d en=%d\n",now,tot,st,en);
 47     int f1,f2;
 48     int i;
 49     int tot1,tot2;
 50     int ss,ee;
 51     if(dp[now][tot]!=-1){
 52         return dp[now][tot];
 53     }
 54     if(tot==1){
 55         if(l[now]==1){
 56             dp[now][tot]=1;
 57             return 1;
 58         }
 59         else{
 60             dp[now][tot]=0;
 61             return 0;
 62         }
 63     }
 64     ss=l[now];ee=r[now];
 65     if(ss%2==0) ss++;
 66     if(ee%2==0) ee--;
 67     for(i=ss;i<=min(ee,en-st);i+=2){
 68         tot1=(i+1)/2;
 69         tot2=tot-tot1;
 70         //printf(" i=%d tot1=%d tot2=%d\n",i,tot1,tot2);
 71         if(tot2<0) break;
 72         if(tot1==1){
 73             f2=fun(now+1,tot2,st+2,en);
 74             if(f2>=1){
 75                 dp[now][tot]=1;
 76                 return 1;
 77             }
 78         }
 79         else if(tot1==tot){
 80             f1=fun(now+1,tot1-1,st+1,en-1);
 81             if(f1>=1){
 82                 dp[now][tot]=i;
 83                 return 1;
 84             }
 85         }
 86         else{
 87             f1=fun(now+1,tot1-1,st+1,st+i-1);
 88             f2=fun(now+tot1,tot2,st+i+1,en);
 89             if(f1>=1 && f2>=1){
 90                 dp[now][tot]=i;
 91                 return 1;
 92             }
 93         }
 94     }
 95     dp[now][tot]=0;
 96     return 0;
 97 }
 98 
 99 void solve()
100 {
101     flag=fun(1,n,1,2*n);
102 }
103 
104 void print(int now,int tot)
105 {
106     int tot1,tot2;
107     tot1=(dp[now][tot]+1)/2;
108     tot2=tot-tot1;
109     printf("(");
110     if(tot1!=1)
111         print(now+1,tot1-1);
112     printf(")");
113     if(tot1!=tot)
114         print(now+tot1,tot2);
115 
116 }
117 
118 void out()
119 {
120    /* int i,j;
121     printf("flag=%d\n",flag);
122     for(i=1;i<=n;i++){
123         for(j=1;j<=n;j++){
124             printf(" i=%d j=%d dp=%d\n",i,j,dp[i][j]);
125         }
126     }*/
127     if(flag==0){
128         printf("IMPOSSIBLE\n");
129     }
130     else{
131         print(1,n);
132         printf("\n");
133         //printf("%s\n",s);
134     }
135 }
136 
137 int main()
138 {
139     //freopen("data.in","r",stdin);
140     //freopen("data.out","w",stdout);
141     //scanf("%d",&T);
142     //for(int ccnt=1;ccnt<=T;ccnt++)
143     //while(T--)
144     while(scanf("%d",&n)!=EOF)
145     {
146         ini();
147         solve();
148         out();
149     }
150     return 0;
151 }

秒客网

Codeforces Round #288 (Div. 2) E. Arthur and Brackets [dp 贪心]

相关文章