POJ 1068 Parencodings

S (((()()())))

P-sequence    4 5 6666

W-sequence    1 1 1456

P_seq表示第i個')'前共有n個'('

W_seq表示第i個'( )'裡包含自己有幾個'( )'

想法：用一個parenthes陣列存每個括弧，找到第i個')'就往前找'('形成'( )'，已經配對的'('就跳過，看中間經過幾個已配對'('就是表示總共包含幾個'( )'

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n,p_seq[25],parenthes[10000],n_p=0,i,j;
	scanf("%d",&t);
	while(t--){
	scanf("%d",&n);
	for(p_seq[0]=0,i=1,n_p=0;i<=n;i++){
	scanf("%d",&p_seq[i]);
	for(j=0;j<p_seq[i]-p_seq[i-1];j++)
	parenthes[n_p++]=0;
	parenthes[n_p++]=1;
	}
	bool matched[10000]={0}; //1:left parenthes is matched
	for(i=0;i<n_p;i++){
	int num=0;
	if(parenthes[i]==1){
	for(j=1;i-j>=0;j++){
	if(parenthes[i-j]==0 && matched[i-j]==0){
	num++;
	matched[i-j]=1;
	printf("%d ",num);
	break;
	}
	else if(parenthes[i-j]==0 && matched[i-j]==1)
	num++;
	}
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068 Parencodings.cpp hosted with ❤ by GitHub

2014/2/17 更新：

用一個diff陣列存每個P値之間的差値，代表兩個')'之間有diff個'('，其他詳見程式碼。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n;
	int p[30];
	int diff[30];
	while (scanf("%d%d" ,&t,&n) != EOF){
	for (int i=0; i<n; i++) scanf("%d",&p[i]);
	diff[0] = p[0];
	for (int i=1; i<n; i++) diff[i] = p[i]-p[i-1];
	printf("1");
	for (int i=1; i<n; i++){
	for (int Count = 1, j = i; j >= 0; --j, ++Count)
	if (diff[j] > 0){
	diff[j]--;
	printf(" %d",Count);
	break;
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068-2 Parencodings.cpp hosted with ❤ by GitHub