poj_1068_Parencodings_問題解決レポート

テーマの出典
タイトル:
文字列Sには2つの符号化方式がある.
1.P-sequence:右括弧に遭遇した場合、現在左のすべての左括弧を記録する
2.W-sequence:右かっこに遭遇した場合、現在の右かっこに一致する左かっこ内の右かっこの数を記録し、自分を含む
解法かいほう:シミュレーション
構想:最も簡単で直接的な方法を用いて、まずP-sequence符号化を原始文字列Sに変換し、更に原始文字列SからW-sequence符号化に変換する
この問題の解法は後で最適化する必要がある.
コード:

/*
360K 0MS
*/
#include <stdio.h>
#include <string.h>

int    p[20];
char   S[100];

void build(int *p, int n); // P 
void getw_sequence();      // W

int main()
{
	int    i;
	int    t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; i++)
			scanf("%d", &p[i]);
		build(p, n);
		getw_sequence();
	}
	return    0;
}

void build(int *p, int n)
{
	memset(S, '\0', sizeof(w));
	memset(S, '(', p[0]);
	S[p[0]] = ')';
	int    i;
	int    w_index = p[0] + 1;
	for (i = 1; i < n; i++)
	{
		memset(&S[w_index], '(', p[i] - p[i-1]);
		w_index += p[i] - p[i-1];
		S[w_index++] = ')';
	}
}

void getw_sequence()
{
	int    i = 0;
	int    n = 1;
	int    k, num = 1; //num W 
	while (S[i] != '\0')
	{
		if (S[i] == ')')
		{
			num = 1, n = 1; // ， num n 1
			k = i,   k--;
			while (n != 0)
			{
				if (S[k] == ')')
					n++, num++;
				if (S[k] == '(')
					n--;
				k--;
			}
			printf("%d ", num);
		}
		i++;
	}
	printf("
");
}