POJ 1068 Parencodings 模拟题

这题勾起我伤心的回忆啊

就是这题，在北信夏令营测试上面作为D题原题，卡了我两三个小时，眼睁睁看着做过此题的ACMER们抢走机会，痛哉~Orz

知耻而后勇，AC300发誓坚持到底，为尊严而战

算法分析：其实这就是个简单的模拟题，用数组做就行，根本没必要用栈，当时还在反复想怎么用栈的STL，晕。用一个数组sequence很容易根据给出的P序列来还原括号序列，1代表作左括号，0代表右括号，每次赋值0之前先赋足够的1在它之前。然后根据sequence数组输出w序列，扫描数组，每遇到一个左括号，就计数它前面还没有匹配的第一个左括号是哪个，然后查这对匹配的括号之间有几个右括号输出即可。

多简单的一道题，却由于没有经验而卡了两三个小时没做出来，痛失良机，这个教训一定要吸取，对计算机专业的学生，算法及编程能力是最核心的竞争力，切记！

#include <iostream>
using namespace std;
int squence[50],p[50];
bool flag[50];
int main(){
	int i,j,k,t,n,loc,left,cnt;
	cin>>t;
	while(t--)
	{
		cin>>n;
		loc = 1;
		left = 1;
		memset(flag,0,sizeof(flag));
		for (i = 1;i <= n;i++)
		{
			cin>>p[i];
			while (left<p[i])
			{
				squence[++loc] = 0;//前面有p[i]个左括号
				left++;
			}
			squence[++loc] = 1;//当前位置赋以右括号
		}
		for (i = 1;i <= 2*n;i++)
		{
			cnt = 0;
			if (squence[i])//只有在右括号的位置才输出
			{
				flag[i] = true;
				for (j = i-1;j > 0;j--)
				{
					if ((flag[j] == false) && (squence[j] == 0))//表示找到了当前还没有匹配的左括号
					{
						flag[j] = true;
						for (k = i;k > j;k--)
						{
							cnt+=squence[k];//然后看匹配的括号之间有几个左括号
						}
						break;
					}
				}
				cout<<cnt<<" ";
			}
		}
		cout<<endl;
	}
	return 1;	
}