POJ 1068

Parencodings

一旦括弧を復元してから，W-sequenceを求めた．
（もっと効率いい方法がありそう…）

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n,m;
	cin >> n;
	for (; n>0; n--) {
		cin >> m;
		string parens = "";
		//P-sequence
		int p0=0, p1;
		for (int i=1; i<=m; i++) {
			cin >> p1;
			for (int j=0; j<p1-p0; j++) parens.append("(");
			parens.append(")");
			p0 = p1;
		}
		//cout << parens << endl;
		//W-sequence
		for (int i=0; i<parens.size(); i++) {
			if (parens[i] == ')') {
				int lparen=0, rparen=1;
				for (int j=i-1; j>=0 && lparen < rparen; j--) {
					if (parens[j] == '(') lparen++;
					if (parens[j] == ')') rparen++;
				}
				cout << rparen << " ";
			}
		}
		cout << endl;

	}
	return 0;
}