作业帮ACM 习题：高手给个思路.不要穷举法,超时!时间限制:1000ms 内存限制:65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 12:08:00
ACM 习题：高手给个思路.不要穷举法,超时!时间限制:1000ms 内存限制:65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面
ACM 习题：高手给个思路.不要穷举法,超时!
时间限制:1000ms 内存限制:65536kB
描述
符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面是”-“ .计算有多少个不同的符号三角形,使其所含”+“ 和”-“ 的个数相同.
n=7时的1个符号三角形如下:
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
输入
每行1个正整数n
ACM 习题：高手给个思路.不要穷举法,超时!时间限制:1000ms 内存限制:65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面
对于符号三角形问题,用n元组x[1：n]表示符号三角形的第一行的n个符号.当x[i]=1时,表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时,表示符号三角形的第一行的第i个符号为“-”号；1 ≤ i≤ n.由于x[i]是二值的,所以在用回溯法解符号三角形问题时,可以用一棵完全二叉树来表示其解空间.在符号三角形的第一行的前i个符号x[1：i ]确定后,就确定了一个由i*（i+1）/2个符号组成的符号三角形.下一步确定了x[i+1]的值后,只要在前面已确定的符号三角形的右边加一条边,就可以扩展为x[1：i+1]所相应的符号三角形.最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4.因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束,用于剪去不满足约束的子树.
另外,对于给定的n,当n*（n+1）/2为奇数时,显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形.
转自http://hi.baidu.com/fandywang%5Fjlu/blog/item/61a9b98bc48a64d5fd1f108a.html