poj 1068 Parencodings

http://162.105.81.212/JudgeOnline/problem?id=1068

首先根据P-sequence构造出这个字符串来,

然后遍历整个字符串,

遇到')'则往回找,直到找出所有'()'为止, (依题目的意思,数据量很小,所以再怎么暴力也不会TLE的-_-)

#include<iostream>
using namespace std;
int main()
{
	int t,n,i,j,tmp,right,ret;
	char c[41];
	scanf("%d",&t);
	while(t--)
	{
		memset(c,'(',sizeof(c));
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&tmp);
			c[i+tmp]=')';
		}
		for(i=1;i<=2*n;i++)
		{
			if(c[i]==')')
			{
				right=1;
				ret=0;
				j=i-1;
				while(right && j>=0)
				{
					if(c[j]=='(')
					{
						right--;
						ret++;
					}
					else
						right++;
					j--;
				}
				if(i==2*n)
					printf("%d/n",ret);
				else
					printf("%d ",ret);
			}
		}
	}
	return 0;
}