符号三角形 - HDU2510【DFS+打表】

题意：一个n*n矩阵的上三角区域，如果a[i][j]==a[i][j+1],那么有a[i+1][j]=正号（1），否则为负号（0）。

思路：强行dfs第一行，然后推出所有。

复杂度分析： 巨TM大。 24次硬是跑了2分多钟… 看到这么小的数据，要想到打表暴力。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[50]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
/*int a[50][50];
int ans=0;

bool judge(int n)
{
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n-i+1;j++)
        {
            if(a[i-1][j]==a[i-1][j+1])
                a[i][j]=1;
            else if(a[i-1][j]!=a[i-1][j+1])
                a[i][j]=0;
        }
    }
    int cnt1=0,cnt0=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n-i+1;j++)
        {
            if(a[i][j]==1)  cnt1++;
            else cnt0++;
        }
    }
    if(cnt1==cnt0)  return true;
    return false;
}

void dfs(int n,int cur)
{
    if(cur==n+1)
    {
        if(judge(n))
            ans++;
        return ;
    }
    for(int i=0;i<=1;i++)
    {
        a[1][cur]=i;
        dfs(n,cur+1);
    }
}*/
int main(void)
{
    /*for(int i=1;i<=24;i++)
    {
        ans=0;
        dfs(i,1);
        cout << ans << endl;
    }*/
    int n;
    while( cin >> n ,n)
    {
        printf("%d %d\n",n,ans[n]);
    }
}