Description

下图展示了一种二叉树： 这种二叉树的每个叶子节点上都标注了权值，而且具有以下有趣的特性：每个非叶子节点，其左右子树叶子节点的权值之和相等。我们称这种二叉树叫平衡二叉树。

我们将一棵平衡二叉树叶子节点的权值从左到右列出来，假如这个权值序列是另一个序列A的子序列，我们称这棵平衡二叉树“隐藏”在序列A当中。在本题中，我们称一个序列S2是另一个序列S1的子序列，当且仅当S2可以由S1中删除0个或多个元素，但不改变S1中剩余元素的相对位置获得。

例如，上图中的平衡二叉树隐藏在序列3 4 1 3 1 2 4 4 6中，因为4 1 1 2 4 4是该序列的子序列。

你的任务是对给定的整数序列，寻找当中隐藏的具有最多叶子节点的平衡二叉树。 n<=1000，1<=ai<=500

Analysis

这道题很容易想到DP，但是这个数据范围显然行不通。我们发现ai<=500，应该从ai入手 依照题目给的图思考 给平衡二叉树分层，每一层的数相等，设最下层的数为x，则每层的数分别为x*2,x*4,x*8…… 那么枚举x，选出来的数只可能是x乘上2的幂，为了方便把所有数除以x，那么只可能是2的幂 而且因为它们最后要构成平衡二叉树，所以它们的和必定也是一个2的幂 而且，除了第一个，为了与前面某一个匹配，该数不可能大于前面所有数的总和 所以，该数为前面所有数的总和的因数，这样只需枚举倍数进行转移

Code