2861146_ac_186ms_248k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 46 行

#include <stdio.h>
#include <string.h>

char tree[20001];
int num[10001], tmp[10001], big[10001];

int main()
{
	int cas = 1, ans;
	int h1, n, i;

	while(scanf("%s",tree)==1,tree[0]!='#')
	{
		h1 = n = 0;
		memset(num,0,sizeof(num));
		ans = -1;
		for(i = 0; tree[i]!='\0'; i++)
		{
			if(tree[i]=='d')
			{
				h1++;
				num[++n] = h1;
				if(num[n]>ans)
					ans = num[n];
			}
			else
				h1--;
		}
		printf("Tree %d: %d => ",cas++,ans);
		ans = -1;
		memset(tmp,-1,sizeof(tmp));
		tmp[0] = 0;big[0] = 0;
		for(i = 1; i <= n; i++)
		{
			if(num[i]==num[i-1]+1)
				tmp[i] = tmp[i-1]+1;
			else
				tmp[i] = big[num[i]]+1;
			big[num[i]] = tmp[i];
			if(tmp[i]>ans)
				ans = tmp[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}