Parencodings POJ - 1068

题目链接 ：https://vjudge.net/problem/POJ-1068

题意：S是一个配对好的括号序列。P序列： P 1 P 2 P 3... P n , P i P1 P2 P3 ...Pn, Pi P1P2P3...Pn,Pi表示第i个右括号之前有多少个左括号。
W序列： W 1 ， W 2 , W 3 , . . . W n W1，W2,W3,...Wn W1，W2,W3,...Wn Wi表示从 第 i 个 右 括 号 对 应 的 左 括 号 的 位 置 第i个右括号对应的左括号的位置 第i个右括号对应的左括号的位置 到 第 i 个 右 括 号 的 位 置 第i个右括号的位置 第i个右括号的位置有多少个右括号。
比如：

S		       (((()()())))

P-sequence	    4 5 6666

W-sequence	    1 1 1456

问题：给你P序列，求出W序列。

思路：读懂之后很容易。由P求出S，由S求出W，模拟这个过程即可。

具体见代码：

#include<iostream>
#include<stack>
using namespace std;
const int maxn=27;
int p[maxn];
int w[maxn];
int pa[maxn];
int r_pos[maxn];
stack<char>stk;
int getw(int id,string s){
	int res=0;
	int l=pa[id];
	int r=r_pos[id];
	//cout<<"l="<<l<<" r="<<r<<endl;
	for(int i=l;i<=r;i++){
		if(s[i]==')')res++;
	}
	//cout<<"res="<<res<<endl;
	return res;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		while(!stk.empty())stk.pop();
		int n;
		cin>>n;
		int i;
		p[0]=0;
		for(i=1;i<=n;i++){
			cin>>p[i];
		}
		//p-->s
		string s="";
		for(i=1;i<=n;i++){
			int j;
			int num=p[i]-p[i-1];
			for(j=1;j<=num;j++){
				s+='(';
			}
			s+=')';
		}
		//cout<<s<<endl;
		int tem=0;//l
		int sum=0;//r
		for(i=0;i<s.size();i++){
			if(s[i]=='(')stk.push(++tem);
			else{
				sum++;
				tem++;
				r_pos[sum]=i;
				int per=stk.top();
				stk.pop();
				pa[sum]=per;
			}
		}
		for(i=1;i<=sum;i++){
			pa[i]-=1;
		}
		for(i=1;i<=n;i++){
			w[i]=getw(i,s);
		}
		for(i=1;i<=n;i++){
			if(i!=n)cout<<w[i]<<" ";
			else cout<<w[i]<<endl;
		}
	}
	return 0;
}