Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13525		Accepted: 8049

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

	S		(((()()()))) 
	P-sequence	    4 5 6666 
	W-sequence	    1 1 1456 

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

2

6 

4 5 6 6 6 6 

9

4 6 6 6 6 8 9 9 9 

1 1 1 4 5 6 

1 1 2 4 5 1 1 3 9

有点乱，感觉方法好多，就是不知道怎么写……

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 int t,n,a[30];
 5 int sec,i,j,k,top;
 6 int stack[50],ans[50];
 7 void printtest()
 8 {
 9     int i;
10     for (i=1;i<=top ;i++ )
11         if (stack[i]==-1) printf("(");
12     else printf(")");
13 }
14 int main()
15 {
16     scanf("%d",&t);
17     for (j=1;j<=t ;j++ )
18     {
19         scanf("%d",&n);
20         a[0]=0;
21         top=0;
22         for (i=1;i<=n ;i++ )
23         {
24             scanf("%d",&a[i]);
25             if (a[i]!=a[i-1])
26             {
27                 for (k=a[i-1]+1;k<=a[i] ;k++ )
28                 {
29                     top++;
30                     stack[top]=-1;//-1表示右括号
31                 }
32                 top++;
33                 stack[top]=1;//1表示左括号
34             }
35             else 
36             {
37                 top++;
38                 stack[top]=1;
39             }
40         }
41         //printtest();//检查
42         ans[0]=0;
43         for (i=1;i<=top ;i++ )
44         if (stack[i]==1)
45         {
46             sec=1;
47             k=i-1;
48             while (sec!=0) 
49             {
50                 sec=sec+stack[k];
51                 k--;
52             }
53             ans[0]++;
54             ans[ans[0]]=(i-k+1)/2;
55         }
56         for (i=1;i<ans[0] ;i++ ) printf("%d ",ans[i]);
57         printf("%d\n",ans[ans[0]]);
58     }
59     return 0;
60 }
61