首页 > 代码库 > HDU 2510 符号三角形 NYOJ491 幸运三角形
HDU 2510 符号三角形 NYOJ491 幸运三角形
符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 860 Accepted Submission(s): 437
Problem 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
很经典的搜索题
提交代码:
#include <stdio.h> 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 main(){ int n; while(scanf("%d", &n), n) printf("%d %d\n", n, ans[n]); return 0; }
打表代码:
#include <stdio.h> int arr[26][26], ans[26], count; void DFS(int n){ if(n > 24) return; for(int i = 0; i <= 1; ++i){ arr[1][n] = i; count += arr[1][n]; for(int j = 2; j <= n; ++j){ arr[j][n-j+1] = arr[j-1][n-j+1] ^ arr[j-1][n-j+2]; count += arr[j][n-j+1]; } if(count * 2 == (1 + n) * n / 2) ++ans[n]; DFS(n + 1); //backTrack count -= arr[1][n]; for(int j = 2; j <= n; ++j){ arr[j][n-j+1] = arr[j-1][n-j+1] ^ arr[j-1][n-j+2]; count -= arr[j][n-j+1]; } } } int main(){ int n; DFS(1); for(int i = 1; i < 25; ++i) printf("%d, ", ans[i]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。