ACM 习题:高手给个思路.不要穷举法,超时!时间限制:1000ms 内存限制:65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/01 22:44:29
![ACM 习题:高手给个思路.不要穷举法,超时!时间限制:1000ms 内存限制:65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“,2个异号下面](/uploads/image/z/14577531-51-1.jpg?t=ACM+%E4%B9%A0%E9%A2%98%EF%BC%9A%E9%AB%98%E6%89%8B%E7%BB%99%E4%B8%AA%E6%80%9D%E8%B7%AF.%E4%B8%8D%E8%A6%81%E7%A9%B7%E4%B8%BE%E6%B3%95%2C%E8%B6%85%E6%97%B6%21%E6%97%B6%E9%97%B4%E9%99%90%E5%88%B6%3A1000ms+%E5%86%85%E5%AD%98%E9%99%90%E5%88%B6%3A65536kB+%E6%8F%8F%E8%BF%B0+%E7%AC%A6%E5%8F%B7%E4%B8%89%E8%A7%92%E5%BD%A2%E7%9A%84%E7%AC%AC1%E8%A1%8C%E6%9C%89n%E4%B8%AA%E7%94%B1%E2%80%9C%2B%E2%80%9D%E5%92%8C%E2%80%9D-%E2%80%9C%E7%BB%84%E6%88%90%E7%9A%84%E7%AC%A6%E5%8F%B7+%2C%E4%BB%A5%E5%90%8E%E6%AF%8F%E8%A1%8C%E7%AC%A6%E5%8F%B7%E6%AF%94%E4%B8%8A%E8%A1%8C%E5%B0%911%E4%B8%AA%2C2%E4%B8%AA%E5%90%8C%E5%8F%B7%E4%B8%8B%E9%9D%A2%E6%98%AF%E2%80%9D%2B%E2%80%9C%2C2%E4%B8%AA%E5%BC%82%E5%8F%B7%E4%B8%8B%E9%9D%A2)
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