HDU 2510 符号三角形 解题报告

Description

符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:
+ + – + – + +
+ – – – – +
– + + + –
– + + –
– + –
– –
+

Input

每行1个正整数n <=24,n=0退出.

Output

n和符号三角形的个数.

Sample Input

15

16

19

20

0

Sample Output

15 1896

16 5160

19 32757

20 59984

Source

ECJTU 2008 Autumn Contest

思路：枚举第一行，后面便随之确定。符号确定规则与异或运算法则相同，所以用0 1表示+ -（顺序无所谓）能简化运算，当0和1个数相同时即为有效状态。本地DFS打表再提交。

AC代码，注释部分为打表代码：

#include <cstdio>
int main()
{
	const int ans[] = {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 n;
	while (scanf("%d", &n) && n)
		printf("%d %d\n", n, ans[n]);
	return 0;
}

/*
#include <cstdio>
using namespace std;
bool map[30][30] = {0};
int ans[30] = {0};
void dfs(int depth, int sum)
{
	if (depth > 24)
		return;
	int add;
	for (int i = 0; i <= 1; i++)
	{
		add = map[1][depth] = i;
		for (int j = 2; j <= depth; j++)
		{
			map[j][depth - j + 1] = map[j - 1][depth - j + 1] ^ map[j - 1][depth - j + 2];
			add += map[j][depth - j + 1];
		}
		if ((sum + add) * 2 == depth * (depth + 1) / 2)
			ans[depth]++;
		dfs(depth + 1, sum + add);
	}
}
void solve()
{
	dfs(1, 0);
	for (int i = 1; i <= 24; i++)
		printf("%d, ", ans[i]);
}
int main()
{
	solve();
	return 0;
}
*/