nyoj--幸运三角形

题意：

幸运三角形

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

 

描述

        话说有这么一个图形，只有两种符号组成（‘+’或者‘-’），图形的最上层有n个符号，往下个数依次减一，形成倒置的金字塔形状，除第一层外（第一层为所有可能情况），每层形状都由上层决定，相邻的符号相同，则下层的符号为‘+’，反之，为‘-’;如下图所示（n = 3 时的两种情况)：

                                           

如果图中的两种符号个数相同，那这个三角形就是幸运三角形，如上图中的图（2）.

 

输入

有多组测试数据（少于20组）。
每行含一个整数n（0<n<20)。

输出

输出相应的幸运三角形个数。

样例输入

3
4

样例输出

4
6
解题思路：
真心不会DFS写，写了就超时，看到数据不多就打表过了。

具体代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int n,sum;
int num[25];
bool Try()
{
    int n0=0,n1=0;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=i;j++)
        {
            if(num[j]==0)
            {
                n0++;
            }
            else
            {
                n1++;
            }
            if(n1>n*(n-1)/2||n0>n*(n-1)/2)
                return false;
            if(j>1)
            {
                if(num[j]==num[j-1])
                    num[j-1]=1;
                else
                    num[j-1]=0;
            }
             
        }
    }
    if(n0 == n1)
         return true;
    return false;
}
void dfs(int cur)
{
    if(cur>n)
    {
        if(Try())
        {
            sum++;
            return;
        }
    }
    else
    {
        num[cur]=0;
        dfs(cur+1);
        num[cur]=1;
        dfs(cur+1);
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        sum=0;
        if(n*(n-1)%2!=0)
        {
            printf("%d
",0);
        }
        else
        {
            dfs(1);
            printf("%d,",sum);
        }
    }
    system("pause");
    return 0;   
}