POJ 1068括弧符号化

1190 ワード

/**
 * parecodings poj 1068
 */
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

typedef vector<int> VecInt;

int main()
{
	VecInt::iterator seq_iter;

	ostream_iterator<int> outer(cout," ");

	int n = 0;
	cin >> n;	/*get loop times*/

	/*loop n times*/
	while (n-- > 0)
	{
        int size = 0;
        int num = 0;
    	VecInt p_seq;

        cin >> size;
        for (int i = 0;i < size;i++)
        {
            cin >> num;
			p_seq.push_back(num);
        }
		VecInt w_seq(size);
		VecInt span(size);

		span[0] = p_seq[0] - 1;
		w_seq[0] = 1;
		for (int i = 1;i < size;i++)
		{
			int legth = p_seq[i] - p_seq[i - 1];
			if (legth > 0)
			{
				span[i] = legth - 1;
				w_seq[i] = 1;
			}
			else
			{
				span[i] = 0;
				w_seq[i] = 1;
				int j = i - 1;
				/*find first span is not zero,we use it calulate the w_sequence*/
				while (span[j] == 0)
				{
					w_seq[i] ++;
					j --;
				}
				w_seq[i] ++;
				span[j] --;
			}
		}
		copy(w_seq.begin(),w_seq.end(),outer);
        cout << endl;
	}
	 return 0;
}