Description
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).
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.
Input
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.
Output
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.
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
今天wj说，这道题模拟就好，用不了多长时间，结果我想了一晚上，用递推的方法做的，不知道他是怎么想的，能A出来，很开心
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = ; void print(int ans[], int n)///打印函数，其实是在中间查错的时候写的，后来就直接用了
{
printf("%d", ans[]);
for(int i = ; i <= n; ++i)
{
printf(" %d", ans[i]);
}
puts("");
} int main()
{
#ifdef LOCAL ///重定向第一发忘记删了，错了T_T
freopen("in.txt", "r", stdin);
#endif
int t, n;
int arr1[maxn], arr2[maxn], ans[maxn];///我的想法是，预处理arr2数组用以放在此坐标左侧有几个半括号
bool tag[maxn]; ///预处理ans数组，每次值变化，都会从“1”开始，然后就处理不是“1”的值
scanf("%d", &t); ///用tag数组标记被处理过的值，
while(t--)
{
memset(tag, false, sizeof(tag));
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%d", &arr1[i]); ans[] = ;
arr2[] = arr1[] - ;
for(int i = ; i <= n; ++i) ///进行一次预处理,将所有为 “1” 的情形记录
{
arr2[i] = arr1[i] - arr1[i-] - ;
arr2[i] = (arr2[i] < ) ? : arr2[i];
ans[i] = (arr1[i] > arr1[i-]) ? : ;
} int i, k;
int sum = ;
for(i = ; i <= n; ++i)
{
if(ans[i] == )
{
for(k = i-; k > ; --k) ///往前找无非两种情况可以累加
{ ///没有被标记过的且arr2值为0，和没有被标记过的且arr2值不为0
if((tag[k] == false) && (arr2[k] == ))
{
sum += ans[k];
tag[k] = true; ///刚开始也DB了， 用于 “==”，查了半天
}
else if((tag[k] == false) && arr2[k])
{
arr2[i] = --arr2[k];
arr2[k] = ;
sum += ans[k] + ; ///找到arr2值不为‘0’，就arr2值转移到 i 身上。到这步就到底了
tag[k] = true;
//printf("%d\n", arr2[i]);
break;
}
}
ans[i] = sum;
sum = ;
}
} print(ans, n);
}
return ;
}