首页 > 代码库 > poj 1068 Parencodings 模拟

poj 1068 Parencodings 模拟

输入的是在每个‘ )  ‘前有多少‘ (  ’,

要我们求得是在每个‘ ) ’前有多少个‘ )  ’,

我的方法是将最原始的图給还原出来,再去寻找‘)’。

对于已经配对的要进行标记不要重复使用。。

#include<stdio.h>
#include<string.h>
int y[505],t[505];
char s[505];
int main()
{
	int a,b,i,j,u;
	scanf("%d",&a);
	while(a--)
	{
		memset(y,0,sizeof(y));
		memset(t,0,sizeof(t));
		memset(s,0,sizeof(s));
		scanf("%d",&b);
		for(i=0;i<b;i++)
		{scanf("%d",&y[i]);
		}
		int sum=1;
		int ans;
		for(i=0,j=0;i<505;i++)
		{
			if(sum<=y[j])
			{
				s[i]='(';
				sum++;
			}
			else
			{
				s[i]=')';
				j++;
			}
			if(j>=b)
				break;
		}
		u=strlen(s);
		for(i=0;i<u;i++)
		{
			if(s[i]=='(')
				continue;
			else
			{
				ans=1;
				t[i]=1;
				for(j=i-1;j>=0;j--)
				{
					if(s[j]==')')
						ans++;
					if(t[j]==0)
					{
						if(s[j]=='(')
						{t[j]=1;break;}
					}
				}
				printf("%d ",ans);
			}
		}
		printf("\n");
	}
	return 0;
}