首页 > 代码库 > nyoj 491 幸运三角形 【DFS】+【打表】
nyoj 491 幸运三角形 【DFS】+【打表】
幸运三角形
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
话说有这么一个图形,只有两种符号组成(‘+’或者‘-’),图形的最上层有n个符号,往下个数依次减一,形成倒置的金字塔形状,除第一层外(第一层为所有可能情况),每层形状都由上层决定,相邻的符号相同,则下层的符号为‘+’,反之,为‘-’;如下图所示(n = 3 时的两种情况):
如果图中的两种符号个数相同,那这个三角形就是幸运三角形,如上图中的图(2).
- 输入
- 有多组测试数据(少于20组)。
每行含一个整数n(0<n<20)。 - 输出
- 输出相应的幸运三角形个数。
- 样例输入
3 4
- 样例输出
4 6
简单的DFS,不打表会超时的。。。
代码:
#include <cstdio> #include <iostream> #include <cstring> const int M = 25; using namespace std; int map[M][M]; int n, ans; int res[] = {0, 0, 0, 4, 6, 0, 0, 12, 40, 0, 0, 171, 410, 0, 0, 1896, 5160, 0, 0, 32757}; /*int judge(){ int i, q = n; int sum1 = 0, sum2 = 0; while(q){ if(map[q][1]) ++sum1; else ++sum2; for(i = 2; i <= q; i ++){ if(map[q][i]) ++sum1; else ++sum2; if(map[q][i]==map[q][i-1]) map[q-1][i-1] = 1; else map[q-1][i-1] = 0; } q--; } if(sum1 == sum2) return 1; else return 0; } void dfs(int cur){ if(cur > n){ if(judge()) ++ans; return ; } map[n][cur] = 1; dfs(cur+1); map[n][cur] = 0; dfs(cur+1); } void f(){ for(int i = 1; i < 20; i ++){ ans = 0; n = i; dfs(1); res[i] = ans; cout<<res[i]<<", "; } }*/ int main(){ // f(); int n; while(cin>>n){ cout<<res[n]<<endl; } return 0; }
nyoj 491 幸运三角形 【DFS】+【打表】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。