符号三角形

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1800    Accepted Submission(s): 930

  
  

   
   15
16
19
20
0
  
  

  
  

   
   15 1896
16 5160
19 32757
20 59984
  
  

分析：dfs代码超时，数据较小，可以打表过，之后再贴优化代码

代码如下：

#include <stdio.h>
int N;
int count=0;
int a[1005][1005];

int judge()
{
	int i,j;
	long long n=0,m=0;
	for(j=0;j<N;j++)
	{//统计第一行的正负个数 
		if(a[0][j])
			n++;
		else
			m++;
	}
		
	for(i=1;i<N;i++)
	{
		for(j=0;j<N-i;j++)
		{//统计其他行的正负个数 
			a[i][j]=!(a[i-1][j]^a[i-1][j+1]);
			if(a[i][j])
				n++;
			else
				m++;
		}
	}
	if(n==m)
		return 1;
	else
		return 0;
}

void dfs(int t)
{//t代表层数，a代表加号个数，b代表减号个数 ,index代表上一层是+还是- 
	if(t==N)
	{
		if(judge())
			count++;
		return ;
	}
	//负号 
	a[0][t]=0;
	dfs(t+1);
	
	//正号 
	a[0][t]=1;
	dfs(t+1);
}

int main()
{
	while(scanf("%d",&N),N)
	{
		count=0;
		dfs(0);
		printf("%d\n",count);
	}
	return 0;
}