Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
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; } */
0 条评论