1694-an old stone game.cpp

总共80多道题的POJ详细解题报告

#include<iostream.h>
#include<stdlib.h>
typedef struct
{
	int r; //所需的石子数
	int son; //指向儿子节点的指针
}NODE;  //节点类型
int sons[202];  //所有节点的儿子
NODE p[201];//保存节点
int comp(const void *e1,const void *e2)
{
	return *(int *)e2 - *(int *)e1;
}
int done(int k)
{
	
	if(p[k].r != -1)
		return p[k].r; //若节点k已求得，直接返回
	int u,v,j;
	int a[200];
	v = p[k].son;
	u = sons[v++];
	for(j=0;j<u;j++)
	{
		if(p[sons[j+v]].r==-1)  
			p[sons[j+v]].r = done(sons[j+v]);//求k的子节点sons[j+v]所需石子数
		a[j] = p[sons[j+v]].r;
	}
	qsort(a,u,sizeof(int),comp);////对a[]快速排序
	int max = 0;
	for(j=0;j<u;j++)
		if(max < a[j] + j)
			max = a[j] + j; /// 取最大的a[j]+j
	return max;
}
void main(void)
{
	
	int t,n;
	int i,j,k,m;
	cin>>t;
	while(t-- >0)
	{
		cin>>n;
		int sn = 0;
		for(i=0;i<n;i++)
		{
			cin>>k>>m;
			if(m==0)
			{
				p[k].r = 1;
				p[k].son = -1;
				continue;
			}
			p[k].son = sn;p[k].r = -1;
			sons[sn++] = m;
			for(j=0;j<m;j++)
				cin>>sons[j+sn]; // 读入节点k的所有子节点
			sn += m;
		}
		j = done(1);//取根节点所需石子数
		cout<<j<<endl;
	}
}