poj1068 Parencodings【简单模拟】

有一串完全匹配的有’（‘和’）‘两种字符的字符串
输入n个数字
代表有n个左括号和n个右括号
此时输入有n个大小的p数组
代表p1 p2…pn
p1代表第一个右括号前面的左括号的数量
要求你求出w数组w1 w2 …wn
w1 代表与第一个右括号 匹配的左括号中间 包含的成对括号数（包含自身）
例子：
（（（）（）（）））
p数组： 3 4 5 5 5
w数组： 1 1 1 4 5

解法：
模拟一遍
根据p数组 长度为n 把长度为2*n的原序列求出来
把为左括号设置为1 右括号设置为2
再根据原序列把w数组求出来
具体操作可以看下面代码：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
#define maxn 1005
#define kk 30
int arr[maxn];
int p[kk], w[kk];

int main() {
	int n, t;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1; i<=n; i++){
			cin>>p[i];
		}
		p[0] = 0;
		memset(arr, -1, sizeof(arr));
		for(int i = 1, j = 0; i <= n; i++){
			for(int k = 0; k < p[i] - p[i-1]; k++){
				arr[j++] = 1;
			}
			arr[j++] = 2;
		}
//		for(int i = 0; i < 2*n; i++){
//			cout<<arr[i]<<" ";
//		}
//		cout<<endl;
		for(int i = 0, l = 0, k;i <2*n; i++){
			k = 0;
			if(arr[i] == 2){
				for(int j = i-1; j >= 0; j--){
					if(arr[j] == 1){
						arr[j] = 0;
						w[l++] = 1+k;
//						cout<<"==="<<k<<endl;
						break;
					}else if(arr[j] == 0){
						k++;
					}
//					printf(%d "%d ==", k);
				}
//				cout<<endl;
			}
		}
		for(int i = 0; i < n; i++){
			printf("%d", w[i]);
			if(i != n-1){
				printf(" ");
			}else {
				printf("\n");
			}
		}
	}
	return 0;
}