当前位置:首页 > 枚举 > 正文
NOI2.5-2990符号三角形
3485+

题目大意:一个三角形有加号减号组成,且两个同号下是加号,异号下是减号,如果最长边是n,请问共有多少种不同的三角形?

题目描述

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

n=7时的1个符号三角形如下:

+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+

输入

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

输出

n和符号三角形的个数.

样例输入

15
16
19
20
0

样例输出

15 1896
16 5160
19 32757
20 59984

提示

实际数据:n<=22

解题思路

按照题目的意思,逐行枚举,先枚举第一行的加减号,枚举时,可以把加号看成0,减号看成1,相同下面是加号,不同下面是减号,恰好位运算的异或运算符的运算规则。第一行的范围是0到(1<<n)-1,下一行可以由上一行通过异或得到:下一行=上一行^上一行*2,然后去头去尾就行。这样,一边推导,一边统计加减号个数(减号个数即1的个数),如果有一个符号超过一半,不用继续搜索(可行性剪枝)。最后如果加减号相同个数,方案数加1。可以预处理2的k次方以及2的n次方以内所有数的二进制中1的个数,时间复杂度O(n*2n)。

这种算法,在暴力算法中还算是高效的,但是剪枝还不够多,因为他枚举的范围还是2n,后面剪枝也只能剪很少部分的枝。能不能剪掉枚举范围的枝呢?可以的,倒过来枚举搜索:从小行到大行枚举,只需要确定每一行的第一个字符,那么同一行后面的都可以逐个推出来。同样,在搜索过程中,遇到加号或者减号超过一半,就退出搜索,这样后面有些行首就不需要枚举了,枚举的范围就少了。当然,时间复杂度还是O(n*2n),但剪枝剪更多了。

实测以上两种算法,分开枚举每一行首字符,速度快一倍。但如果要更快,可以尝试记忆化搜索,如预处理前几行的加减号个数等。如果用位运算,预处理出n=20的所有符号三角形的加减号个数,再在此基础上算n=23、24的符号三角形数目,速度会快很多。

程序实现

NOI2.5-2990符号三角形:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!