nyoj-----幸运三角形

幸运三角形

时间限制:1000 ms  |  内存限制:65535 KB

难度:3

描述

        话说有这么一个图形,只有两种符号组成(‘+’或者‘-’),图形的最上层有n个符号,往下个数依次减一,形成倒置的金字塔形状,除第一层外(第一层为所有可能情况),每层形状都由上层决定,相邻的符号相同,则下层的符号为‘+’,反之,为‘-’;如下图所示(n = 3 时的两种情况):

如果图中的两种符号个数相同,那这个三角形就是幸运三角形,如上图中的图(2).

输入有多组测试数据(少于20组)。

每行含一个整数n(0<n<20)。输出输出相应的幸运三角形个数。样例输入

3
4

样例输出

4
6

来源原创上传者ACM_杨延玺dfs搜索。。。。

代码:

 1 #include<stdio.h>
 2 int str[20]={0};
 3 bool map[20][20];
 4 void dfs(int x,int pos)
 5 {
 6     int i;
 7     if(x==pos)
 8     {
 9         int ans=0;
10         do{
11            if(map[pos][pos]) ans++;
12           for(i=1;i<pos;i++) //下一城
13           {
14               if(map[pos][i]==map[pos][i+1]) map[pos-1][i]=1; //tong wei 1
15               else   map[pos-1][i]=0;
16               if(map[pos][i]) ans++;
17               if(4*ans>x*(x+1)) return ;
18           }
19         }while(--pos);
20         if(4*ans==x*(x+1)) str[x]++;
21         return ;
22     }
23     map[x][pos+1]=0;   //采用横向搜索
24     dfs(x,pos+1);
25     map[x][pos+1]=1;
26     dfs(x,pos+1);
27 }
28 int main()
29 {
30     int n,i;
31     for(i=1;i<19;i++)
32     {
33         if(i%4==3||i%4==0)dfs(i,0);
34     }
35     str[19]=32757;
36     while(scanf("%d",&n)!=EOF)
37     {
38         printf("%d\n",str[n]);
39     }
40     return 0;
41 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.3K8
来自专栏freesan44

python 算法开发笔记

1752
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之算术编码

早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对芯源的编码,并从理论上论证了它的优越性。1960年, Peter E...

1163
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

3602
来自专栏python读书笔记

《算法图解》note 9 动态规划1.动态规划定义2.与分治法及贪婪算法的区别3.动态规划的后续学习

2015
来自专栏小樱的经验随笔

从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的! 简单点说...

43510
来自专栏null的专栏

数据结构和算法——用动态规划求解最短路径问题

一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

4675
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3828
来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

952
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

1231

扫码关注云+社区

领取腾讯云代金券